吳辰文，李 壯，梁雨欣

(蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

由于網(wǎng)絡(luò)技術(shù)和計算機超強算力的發(fā)展,每天都有大量來自醫(yī)療、商業(yè)及生活方面的數(shù)據(jù)產(chǎn)生。如果只依靠手動的方式從如此量級的數(shù)據(jù)集中獲取有效信息,其時間和人力成本是高昂的。因此，勢必要借助現(xiàn)代化技術(shù)的計算能力。在眾多對信息進行有效提取的方式中,聚類算法可以從海量級的數(shù)據(jù)中快速找到數(shù)據(jù)間的相關(guān)性，建立有用的數(shù)據(jù)模型。目前，使用頻率高且典型的無監(jiān)督算法有基于數(shù)據(jù)密度聚類算法(DBSCAN)、高斯混合模型最大期望聚類、凝聚層次聚類、模糊c均值聚類(fuzzy c-means clustering, FCM)和K均值聚類(K-means)。傳統(tǒng)的聚類方法是在經(jīng)典集合理論的基礎(chǔ)上進行硬劃分,即假設(shè)一個對象只屬于一個聚類。但是在實際應(yīng)用中,很多聚類問題在具體操作的過程中并沒有特定的邊界,無法將所有數(shù)據(jù)明確定義到一個具體的類別當(dāng)中，因此，模糊聚類比硬聚類更自然。例如醫(yī)療的特殊領(lǐng)域，傳統(tǒng)的硬聚類標(biāo)準(zhǔn)無法滿足對基因和疾病樣本聚類的需求。每個基因并不只擁有單一的功能和作用，可能同時擔(dān)負多個任務(wù)。在藥物治療中,每種藥物并不只局限于治療一種疾病,而是對不同的疾病有不同的治療效果。正是由于這些因素,使得模糊聚類與傳統(tǒng)的硬聚類相比,更適用于藥物和疾病基因的聚類。

所謂的模糊聚類是基于模糊集理論,使用數(shù)理統(tǒng)計的手段或方法對數(shù)據(jù)進行多元分析,通過數(shù)學(xué)方式定義樣本間的強弱聯(lián)系,再由聯(lián)系的“強弱”對數(shù)據(jù)進行聚類。在具體的算法表達中,強弱是一個[0,1]的取值,用于表示屬于某個類別程度的大小。在模糊聚類中,通過計算得到不同的隸屬度值,使數(shù)據(jù)點可以在不同程度上屬于多個標(biāo)簽。傳統(tǒng)FCM使用歐氏距離,容易受到噪聲和離群點干擾,為解決這個問題，有學(xué)者將FCM算法改進為KFCM(kernel fuzzy c-means clustering)[1]，與FCM相比有更好的聚類性能。然而，KFCM算法依然存在一些問題:①在數(shù)據(jù)聚類過程中需要人為指定聚類個數(shù),但由于現(xiàn)在的數(shù)據(jù)集體量過大,人為指定聚類個數(shù)不準(zhǔn)確,會嚴重影響算法的聚類精度和性能；②聚類效果和精度容易被噪聲數(shù)據(jù)點和環(huán)境因素影響。

1 相關(guān)工作

FCM算法由Dunn在1973年闡述并提出[2]。 2008年, 呂回等人為了優(yōu)化并緩解FCM算法所存在的主要缺陷, 如數(shù)據(jù)初始化敏感， 且在進行聚類或運算時會出現(xiàn)局部最優(yōu)解, 在FCM中加入了核函數(shù)的概念, 通過核把低維空間中不明顯的特征突顯出來, 得到更好的聚類效果[3]。2010年, 黃保海等人為解決聚類中高維數(shù)據(jù)非線性的缺陷, 提出以核主元分析(KPCA)為基礎(chǔ)并結(jié)合KFCM集成的方法,利用核主元分析的優(yōu)點直接對高維數(shù)據(jù)的特征進行篩選[4]。2013年靳璐等人針對紅外圖像的模糊聚類對初始中心敏感的問題,提出一種使用圖像灰度進行分析然后聚類的遺傳模糊核聚類算法,這個算法可以求解出全局最優(yōu)聚類中心，并且計算得到其隸屬度矩陣[5]。2015年,任昌榮提出一種使用多種群協(xié)同量子粒子群模擬退火(MCQPSO-SA)對KFCM進行優(yōu)化，優(yōu)化后的KFCM算法提高了局部和全局尋找最優(yōu)解的能力[6]。2018年趙海峰等人重新設(shè)計了KFCM中的局部隸屬度函數(shù)， 提出基于加權(quán)的模糊隸屬度KFCM分割算法, 在提高算法魯棒性的同時維持了算法的精度[7]。 2019年, 何云斌等人利用平均距離對KFCM進行優(yōu)化, 其目的是解決算法對隨機獲取的聚類中心敏感的缺陷, 使KFCM算法能夠自動獲取比較優(yōu)秀的聚類中心[8]。2021年Ciri等人提出了一種利用KFCM聚類的基于特征值的協(xié)作頻譜感知(CSS)新技術(shù)，將信道分為可用和不可用兩類，并在多維空間中提高了檢測性能[9]。

本文在參考文獻[2-3,8]的前提下,將KFCM與Canopy算法結(jié)合,使KFCM擁有自動確定聚類類別的能力。對KFCM的隸屬度函數(shù)進行改進,將離群數(shù)據(jù)點和異常值數(shù)據(jù)點的數(shù)據(jù)隸屬度由其最近鄰的n個數(shù)據(jù)點的隸屬度的均值來替換,使離群數(shù)據(jù)點和異常值數(shù)據(jù)點對KFCM算法的聚類性能和聚類效果的影響大大降低。

1.1 KFCM聚類算法

在FCM算法中引入一種基于核的相似性度量函數(shù)代替原先的歐氏距離[10]，其中的核即為一種映射函數(shù)，將原數(shù)據(jù)集中無法通過一個線性函數(shù)劃分的數(shù)據(jù),通過數(shù)學(xué)方法變換到高維空間中，使其不顯著但是有聚類意義的特征突顯。這樣不僅能夠使算法處理線性不可分問題,還便于對聚類結(jié)果進行描述。

KFCM的目標(biāo)函數(shù)公式為

(1)

其中：C∈[x,N)是數(shù)據(jù)的聚類總數(shù);N是數(shù)據(jù)點的總數(shù);uki是xi相對于vk的隸屬度,且uki∈[0,1]；φ表示高維度空間非線性特征映射。

1.2 Canopy算法

Canopy算法是Mccallum在2000年提出的粗聚類算法[11],Canopy算法通?？梢宰鳛槠渌麩o監(jiān)督聚類算法之前的預(yù)處理,它能夠在犧牲可接受程度內(nèi)的精度對樣本進行快速的聚類計算,作為輔助其他聚類算法的預(yù)處理[12]。Canopy算法使用距離將數(shù)據(jù)進行劃分,并得到計算后的分類,再由后續(xù)聚類算法對數(shù)據(jù)進行處理[13]。Canopy算法與其他經(jīng)典聚類算法結(jié)合可以對其他算法進行優(yōu)化并縮短運行時間[14],也以用于直接聚類。在研究高維和大量的數(shù)據(jù)時,Canopy算法對數(shù)據(jù)分布情況以及確定樣本的分組有極大價值[15]。

Canopy算法步驟如下:

Step1設(shè)置Canopy的距離閾值T1和T2,且T1>T2。

Step2在原始數(shù)據(jù)集中任取一點p,作為第一個聚類中心，并將其從原始數(shù)據(jù)集中刪除。

Step3繼續(xù)從原始數(shù)據(jù)集取點,計算其到所有已產(chǎn)生的聚類中心點的距離d。

1) 如果d

2) 如果T2

3) 如果d>T1,則該點成為新聚類中心點，并從原始數(shù)據(jù)集中刪除。

Step4重復(fù)步驟3,直至原始數(shù)據(jù)集為空。

2 算法改進

為解決KFCM算法需要手動輸入聚類類別的問題,本文擬將Canopy快速粗聚類算法與KFCM算法相結(jié)合,使其自動確定聚類類別;其次，改進KFCM算法的隸屬度函數(shù)[16],使其對類邊緣點擁有更高的分類準(zhǔn)確率,提高算法分類性能。

2.1 相似性度量方法

聚類算法的一個重要步驟就是如何確定一種可靠有效的衡量數(shù)據(jù)對象之間相似性[17]的計算方式。KFCM算法相似性度量方法采用核函數(shù)的形式,比如高斯核函數(shù)[18]、多項式核函數(shù)[19]和線性核函數(shù)[20]等,其公式定義如下。

線性核函數(shù)(linear kernel)

k(x,y)=xTy+c。

(2)

其中：c為常數(shù)項；xTy為內(nèi)積。

多項式核函數(shù)(polynomial kernel)

k(x,y)=(γx·y+c)d。

(3)

高斯核函數(shù)(Gaussian kernel)

(4)

其中：y為高斯核函數(shù)的中心;σ為高斯核的寬度參數(shù),其大小由人工設(shè)置,并且控制函數(shù)在數(shù)據(jù)中的作用范圍,過大或過小都會影響算法的性能。

而本文改進的KFCM算法是使用式(4)的高斯核函數(shù)。它對離群數(shù)據(jù)點和異常值數(shù)據(jù)點有著優(yōu)秀的抗干擾能力,使算法更具魯棒性。但缺點是函數(shù)在聚類和計算中的作用范圍由其參數(shù)的大小決定,如果超出設(shè)定參數(shù)的最大范圍,其核函數(shù)的作用就微乎其微，且函數(shù)對參數(shù)敏感,不容易達到預(yù)期效果。

2.2 改進KFCM的隸屬度函數(shù)

在對式(1)進行求解后,得到矩陣中隸屬度值和聚類簇心點的計算公式，

(5)

(6)

在KFCM中,核函數(shù)的本質(zhì)[21]是進行非線性的變換φ:x→φ(x)，就是將原算法距離公式‖x-y‖2以‖φ(x)-φ(y)‖2代替

‖φ(x)-φ(y)‖2=

(φ(x)-φ(y))T(φ(x)-φ(y))=

φ(x)Tφ(x)-φ(x)Tφ(y)-φ(y)Tφ(x)+

φ(y)Tφ(y)。

(7)

KFCM算法對數(shù)據(jù)進行聚類或者分類時,由于算法本身只看重數(shù)據(jù)的屬性或特征,過于注重特征就會忽略局部數(shù)據(jù)間的相關(guān)性和數(shù)據(jù)與數(shù)據(jù)間隱藏的聯(lián)系。而且KFCM算法的效率和性能又易受離群數(shù)據(jù)點和異常值數(shù)據(jù)點的影響。針對這些問題,本文對KFCM算法的隸屬度函數(shù)進行改進。用任意數(shù)對空隸屬度模糊矩陣U進行初始化,且數(shù)值范圍為[0,1],使隸屬度矩陣初始完成后滿足以下要求，

(8)

若算法判定一個數(shù)據(jù)點為噪聲點,則使用該數(shù)據(jù)點鄰域內(nèi)的隸屬度平均值進行計算，

(9)

其中,E為噪聲點i的鄰域。

由于在K-means和KFCM聚類中,算法會將每個數(shù)據(jù)點分配到具體的簇類中,因此，本文提到的數(shù)據(jù)噪聲點主要為聚類的邊緣錯分點,以解決類邊緣數(shù)據(jù)點相互影響導(dǎo)致分類錯誤的問題。噪聲點的判斷方法為：取可能為噪聲點數(shù)據(jù)最近鄰的n個數(shù)據(jù)點,同時計算n個數(shù)據(jù)點的類型,若有n/2個數(shù)據(jù)點的類型與此點不同,則其為噪聲點。對噪聲點通過式(9)的隸屬度函數(shù)進行計算后,可以使KFCM算法更具魯棒性。

2.3 Canopy算法與KFCM算法相結(jié)合的C-KFCM算法

KFCM算法是一種以模糊集理論為基礎(chǔ)并佐以數(shù)學(xué)分析手段的聚類算法。 模糊聚類從根本上講是軟聚類， 即每個數(shù)據(jù)樣本都有對類別劃分的概率， 且所有概率相加為1。 同時， 這些概率也會在計算時說明數(shù)據(jù)在給定聚類群中的存在程度。 與傳統(tǒng)的硬聚類相比, 模糊聚類更能表達出數(shù)據(jù)的本質(zhì)意義, 也能為后續(xù)的數(shù)據(jù)處理和數(shù)據(jù)挖掘給予更多有用的信息。 但KFCM算法仍需人工指定聚類個數(shù)且對噪聲敏感。 為此, 本文將KFCM和Canopy算法相結(jié)合，提出C-KFCM算法。無需人工干預(yù),由Canopy算法給出初始聚類個數(shù)作為KFCM算法的輸入,防止人工干預(yù)的不確定性影響算法的效果和性能,提高KFCM算法的準(zhǔn)確性。

C-KFCM算法步驟如下:

Step1用Canopy粗聚類算法計算原始數(shù)據(jù)集聚類個數(shù)C和集群S。

Step2將C和S作為KFCM算法的初始輸入,并設(shè)置模糊參數(shù)m、核函數(shù)條件σ、收斂邊界值ε和迭代數(shù)t。

Step3使用[0,1]的隨機數(shù)對隸屬度矩陣進行初始操作,并使用式(5)計算隸屬度矩陣。

Step4使用式(9)重新對隸屬度矩陣中的噪聲點進行計算。

Step5使用式(6)對數(shù)據(jù)的聚類中心進行計算。

Step6判斷若|Cn-Cn-1|<ε，則算法收劍，結(jié)束算法，否則執(zhí)行Step3。

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

3.1 實驗介紹

實驗條件:Windows 10,i5-4200M,4 GB,Python 3.6.2: Anaconda custom。為對本文提出的C-KFCM算法進行綜合全面的評價，將數(shù)據(jù)集分為兩大類,一類為真實數(shù)據(jù)集，另一類為人工合成數(shù)據(jù)集。使用這些數(shù)據(jù)集對算法的性能和聚類效果進行實驗,數(shù)據(jù)集屬性如表1所示。實驗使用的人工合成數(shù)據(jù)集包括Spiral、Jain、D31、Isquare2和Aggregation,真實數(shù)據(jù)集包括Iris和Wine。

表1 實驗數(shù)據(jù)集屬性Tab.1 Experimental data set properties

3.2 聚類評價指標(biāo)

為準(zhǔn)確且全面地評價本文的C-KFCM算法,使用準(zhǔn)確率(ACC)[22]和調(diào)整蘭德系數(shù)(adjusted rand index,ARI)[23]對C-KFCM算法的聚類效果進行比較和分析。

聚類準(zhǔn)確率(ACC)計算公式為

(10)

調(diào)整蘭德系數(shù)(ARI)計算公式為

(11)

其中：U集合為數(shù)據(jù)的真實標(biāo)簽；V集合為聚類結(jié)果；a為在U集合和V集合中是相同簇類的數(shù)據(jù)對個數(shù);b為在U集合中為同簇類的數(shù)據(jù)對,但在V集合中是異簇類的數(shù)據(jù)對個數(shù);c為在U集合中屬于異簇類的數(shù)據(jù)對,但在V集合中是同簇類的數(shù)據(jù)對個數(shù);d為在U集合和V集合中都是異簇類的數(shù)據(jù)對個數(shù)。

ACC和ARI兩種聚類指標(biāo)皆為[0,1]的取值，且越接近1算法性能越高。

3.3 C-KFCM聚類類別分析

實驗使用4個人工數(shù)據(jù)集對C-KFCM的聚類數(shù)量準(zhǔn)確率進行評測，目的在于驗證與粗聚類算法Canopy結(jié)合后的KFCM算法在識別數(shù)據(jù)集類別時，是否具有一定的準(zhǔn)確率和穩(wěn)定性。由于Canopy算法屬于粗聚類算法,本身缺乏一定聚類的精度，因此，在結(jié)合后的算法中,采用運行一次C-KFCM算法,運行n次Canopy算法，獲得n個聚類數(shù)量結(jié)果,再求取n次結(jié)果平均值的辦法來提高準(zhǔn)確性，n的取值為10。表2為C-KFCM算法的聚類類別數(shù)量結(jié)果。 通過圖1對比每組平均集群數(shù)和數(shù)據(jù)真實集群數(shù)， 可以看出， 聚類數(shù)據(jù)的平均值大多都非常接近真實的集群數(shù)量, 且誤差在±0.5以內(nèi)。 再對聚類平均結(jié)果取整， 得到C-KFCM聚類數(shù)目。實驗表明,Canopy和KFCM結(jié)合后的算法在獲得真實集群數(shù)量上有一定的準(zhǔn)確性和穩(wěn)定性。

表2 C-KFCM算法聚類類別數(shù)量Tab.2 Clusters number of C-KFCM algorithm

圖1 C-KFCM平均集群數(shù)與真實集群數(shù)對比Fig.1 C-KFCM average clusters number compared with actual clusters number

3.4 C-KFCM與KFCM準(zhǔn)確率分析

實驗在4個人工數(shù)據(jù)集和兩個真實數(shù)據(jù)集上進行，將C-KFCM算法和Canopy、K-means、DBSCAN和KFCM算法進行對比，評價聚類性能和效果。采用主成分分析法將數(shù)據(jù)集屬性降至二維以便計算。其中，D31、Isquare2、Spiral和Aggregation人工數(shù)據(jù)集中,特征數(shù)量為2,但D31樣本和類別較多且類邊緣交疊，真實數(shù)據(jù)集Iris和Wine擁有多個特征屬性。

聚類實驗的效果如圖2所示。對比6組可視化聚類實驗分析可以得出，Canopy算法本身就屬于粗聚類算法,聚類速度占有優(yōu)勢,但聚類精度卻處于劣勢。K-means算法由于對非凸數(shù)據(jù)集難以收斂且容易陷入局部最優(yōu),因此，對識別Spiral和Isquare2數(shù)據(jù)集的形狀聚類能力較差。DBSCAN是對數(shù)據(jù)分布密度感知較強的算法,因此，對數(shù)據(jù)密度分布差異不大的數(shù)據(jù)聚類效果較好,如Aggregation、Spiral、Isquare2數(shù)據(jù)集。但由于此算法的內(nèi)部參數(shù)ε需要手動調(diào)整，且對數(shù)據(jù)密度敏感,過大或過小都會導(dǎo)致聚類失敗,在Iris和Wine數(shù)據(jù)集中聚類效果較差。對于KFCM算法,雖然通過核函數(shù)對其突顯特征在高維空間進行聚類,但由于對數(shù)據(jù)噪聲敏感，且類邊緣數(shù)據(jù)點相互影響，導(dǎo)致部分數(shù)據(jù)點分類錯誤,如在Aggreation和Wine數(shù)據(jù)集上的聚類效果。C-KFCM算法在所有聚類算法中表現(xiàn)出較好的穩(wěn)定性和準(zhǔn)確率,并能成功識別出數(shù)據(jù)的原有形狀,且糾正了KFCM聚類錯誤的邊緣點和錯分點。

圖2 5種算法對不同數(shù)據(jù)集的聚類結(jié)果Fig.2 The clustering results of five clustering algorithms on different dataset

綜合實驗結(jié)果對比聚類算法性能,由圖3和圖4可以看出,本文改進算法C-KFCM在準(zhǔn)確率和調(diào)整蘭德系數(shù)兩種指標(biāo)上均表現(xiàn)出比較優(yōu)秀的聚類性能,與原KFCM算法相比聚類效果要更好一些。由于Canopy、K-means、DBSCAN和KFCM算法本身的側(cè)重點不同，都存在各自的缺陷，因此，在特定數(shù)據(jù)集上表現(xiàn)不甚樂觀。實驗證明,本文改進的C-KFCM算法在大部分數(shù)據(jù)集都達到了比較優(yōu)秀的聚類效果和較高的聚類準(zhǔn)確率。

圖3 ACC指標(biāo)對比Fig.3 Comparison of ACC indicators

圖4 ARI指標(biāo)對比Fig.4 Comparison of ARI indicators

4 結(jié)語

本文針對KFCM算法需要人工干預(yù)聚類簇數(shù)，且聚類效果不穩(wěn)定的問題，提出C-KFCM算法。將KFCM算法與Canopy算法相結(jié)合，再改進算法的隸屬度函數(shù),將數(shù)據(jù)邊緣點的隸屬度由近鄰點的平均隸屬度代替,提高了算法的準(zhǔn)確率和穩(wěn)定性。通過與改進前的KFCM算法進行對比,糾正了KFCM算法在聚類時產(chǎn)生的少量噪聲點和錯分點,相較于原始算法準(zhǔn)確率有所提升。同時，在與相關(guān)算法對比不難發(fā)現(xiàn),C-KFCM在準(zhǔn)確率方面對易分的數(shù)據(jù)集形狀與對比算法基本沒有差距,而在不規(guī)則形狀的數(shù)據(jù)集上,準(zhǔn)確率要優(yōu)于對比算法。但C-KFCM依然存在不足,獲取聚類集群數(shù)量是通過迭代求取平均值的方式,這在面對大規(guī)模數(shù)據(jù)集時無疑會付出巨大的時間和算力消耗,因此，如何優(yōu)化算法自動集群，降低算法的復(fù)雜度和性能消耗是接下來的研究重點。