融合可拓關(guān)聯(lián)函數(shù)的密度峰值聚類算法

趙燕偉,朱 芬,桂方志,任設(shè)東,謝智偉,徐 晨

1(浙江工業(yè)大學(xué) 特種裝備制造與先進(jìn)加工技術(shù)教育部 浙江省重點(diǎn)實(shí)驗(yàn)室,杭州 310014)2(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310014)

1 引 言

聚類是數(shù)據(jù)分析的重要手段,將數(shù)據(jù)集分為若干類,使得簇內(nèi)緊密且相似性大,簇與簇之間有明顯區(qū)別,使得相似性最小[1],在模式識別、圖像處理和風(fēng)險(xiǎn)管理等領(lǐng)域被廣泛應(yīng)用[2-5].大數(shù)據(jù)背景下的海量和多樣數(shù)據(jù)的存在,使得聚類算法的研究對這些數(shù)據(jù)背后隱藏的模式和規(guī)律的發(fā)現(xiàn)具有重要意義.

聚類算法有劃分式、密度式,網(wǎng)格式等[6,7],其中劃分式聚類算法主要以K-means算法為代表,密度式聚類算法主要以DBSCAN[8,9]算法為代表,網(wǎng)格式主要以CLIQUE[10]算法為代表.盡管許多聚類算法被提出,但對聚類的研究仍在不斷地探索中.2014年Alex Rodriguez 和 Alessandro Laio等[11]提出了一種密度峰值聚類算法CFSFDP,憑借其能自動(dòng)發(fā)現(xiàn)數(shù)據(jù)集樣本的類簇中心,實(shí)現(xiàn)任意形狀的樣本高效聚類等優(yōu)勢,引起了大量學(xué)者的關(guān)注,但是該算法存在明顯缺陷:當(dāng)數(shù)據(jù)集中存在多個(gè)密度峰值或者某一個(gè)非中心樣本點(diǎn)分配錯(cuò)誤就會(huì)出現(xiàn)連續(xù)分錯(cuò)現(xiàn)象[12].對此學(xué)者提出了不同的改進(jìn)方法:賈培靈等[13]針對某個(gè)類存在多個(gè)密度峰值導(dǎo)致聚類不理想問題,提出一種基于簇邊界劃分的DPC算法;薛小娜等[14]提出了一種結(jié)合k近鄰的改進(jìn)密度峰值聚類算法,結(jié)合k鄰域思想設(shè)計(jì)了全局搜索分配策略;Wang S L等[15]提出了一種利用原始數(shù)據(jù)集中數(shù)據(jù)場的潛在熵自動(dòng)提取閾值最優(yōu)值的新方法;MehmoodR等[16]提出了一種自適應(yīng)選擇聚類中心的模糊CFSFDP方法,具有較好的魯棒性和有效性;謝娟英等[17]提出一種基于k近鄰的快速密度峰值搜索并高效分配樣本的聚類算法,對噪聲數(shù)據(jù)具有非常好的魯棒性;Mehmood R等[18]提出了一種通過熱擴(kuò)散密度峰值算法,用于采用非參數(shù)估計(jì)給定數(shù)據(jù)集的概率分布,對截止距離的選擇和核密度估計(jì)進(jìn)行校正;Zhou Y等[19]提出了一種基于密度比的方法來聚類,通過使用密度估計(jì)器計(jì)算密度比,修改基于密度的聚類算法以進(jìn)行基于密度比的聚類;Du M等[20]提出了一種基于k個(gè)最近鄰點(diǎn)的密度峰聚類,并將主成分分析(PCA)引入到DPC-KNN模型中,進(jìn)一步提出了基于PCA的方法,該方法對高維數(shù)據(jù)有更好的聚類效果;劉如輝等[21]提出半監(jiān)督約束集成的快速密度峰值聚類算法,自動(dòng)選擇候選中心點(diǎn)提高聚類性能具有更高的聚類精度.Chen等[22]摒棄對單個(gè)初始中心點(diǎn)的尋找,通過用一半高密度的點(diǎn)生成初始聚類輪廓,完成聚類.

現(xiàn)有的研究雖取得了一定的成效,但簇心選取及未分配點(diǎn)分配準(zhǔn)確率仍然不高,一方面原因是簇心質(zhì)量不佳,另一方面是由于其所采取的最近鄰原則分配策略本質(zhì)上都是基于歐式距離計(jì)算而來的密度值,并沒有從本質(zhì)上挖掘出樣本點(diǎn)間的相關(guān)性,造成樣本分配錯(cuò)誤.因此本文提出一種融合可拓關(guān)聯(lián)函數(shù)的密度峰值聚類算法,引入基于平均差異度的密度度量方式,并提出一種基于可拓關(guān)聯(lián)函數(shù)和k鄰域思想的分配策略,實(shí)現(xiàn)對未分配點(diǎn)進(jìn)行準(zhǔn)確分類.通過對比實(shí)驗(yàn)驗(yàn)證,該方法具有更好的聚類效果和聚類準(zhǔn)確率.

2 相關(guān)知識介紹

2.1 可拓關(guān)聯(lián)函數(shù)相關(guān)知識介紹

為刻畫論域中的元素具有某種性質(zhì)的程度,蔡文[23]等提出了可拓關(guān)聯(lián)函數(shù)的概念,通過建立實(shí)域上可拓集的關(guān)聯(lián)函數(shù)基本公式,定量客觀的描述元素具有某種性質(zhì)的程度及其量變與質(zhì)變的過程.該概念在分類檢索和故障預(yù)警等方面廣泛應(yīng)用,趙燕偉等[24]提出一種基于可拓距的多維關(guān)聯(lián)函數(shù)產(chǎn)品低碳設(shè)計(jì)分類方法,解決了低碳設(shè)計(jì)中因需求變化所引起的分類跳躍性問題;任設(shè)東等[25]提出一種基于關(guān)聯(lián)函數(shù)多屬性相似實(shí)例檢索方法,克服了歐式距離檢索的不準(zhǔn)確性;洪歡歡等[26]提出了一種多維關(guān)聯(lián)函數(shù)建模及其檢索應(yīng)用方法,解決多維度實(shí)例檢索建模及其降維計(jì)算的問題.可見,可拓關(guān)聯(lián)函數(shù)在描述事物相似度具有較大優(yōu)勢,將其與聚類算法結(jié)合,充分發(fā)揮其優(yōu)勢是目前研究的重要方向.

在建立關(guān)聯(lián)函數(shù)前,為了描述類內(nèi)事物的區(qū)別,引入可拓距和位值等概念:

實(shí)軸上任意一點(diǎn)x與區(qū)間X0=之距為:

(1)

設(shè)X0=,X=,且X0?X則稱:

D(x,X0,X)=

(2)

為點(diǎn)x關(guān)于區(qū)間X0和X組成的區(qū)間套的位值.

設(shè)X0=,X=,且X0?X,則:

(3)

稱k(x)為點(diǎn)x關(guān)于區(qū)間X0和X的關(guān)聯(lián)函數(shù).通過關(guān)聯(lián)函數(shù)描述事物具有某種性質(zhì)的程度,即將“具有某性質(zhì)”的事物從定性描述擴(kuò)展到“具有該性質(zhì)的程度”的定量描述.k(x)≥0表明x屬于區(qū)間X0,k(x)<0表明x不屬于區(qū)間X0.

(4)

稱K(O)為對象O的綜合關(guān)聯(lián)函數(shù),vi為對象O第i個(gè)屬性對應(yīng)的值.

2.2 CFSFDP算法介紹

CFSFDP算法以其決策圖思想和一步分配策略思想,引起很多學(xué)者的關(guān)注,即提出決策圖概念自動(dòng)發(fā)現(xiàn)數(shù)據(jù)集中樣本的類簇中心,并快速分配非中心點(diǎn),實(shí)現(xiàn)任意形狀的高效聚類[12].

該算法認(rèn)為理想的類簇中心應(yīng)具備兩個(gè)基本特征:

1)該點(diǎn)局部密度大于圍繞它的樣本點(diǎn)的局部密度;

2)不同簇心間距離相對較遠(yuǎn).為找到滿足上述要求的點(diǎn),對于每個(gè)數(shù)據(jù)i都引入了局部密度ρi和相對距離δi兩個(gè)概念:

(5)

(6)

其中dc為截?cái)嗾`差,dij是數(shù)據(jù)i和j之間的歐式距離.

(7)

可知當(dāng)數(shù)據(jù)i的局部密度ρi不是最大值時(shí),其相對距離δi為在所有的局部密度大于數(shù)據(jù)對象i的數(shù)據(jù)對象中,與數(shù)據(jù)對象i的距離最小的數(shù)據(jù)與數(shù)據(jù)i間的距離;當(dāng)數(shù)據(jù)i的局部密度ρi最大時(shí),δi為數(shù)據(jù)集中與數(shù)據(jù)i距離最大的距離.

CFSFDP算法認(rèn)為簇心往往是δ異常大的樣本點(diǎn),同時(shí)這些樣本點(diǎn)的局部密度ρ也相對較高.通過構(gòu)造樣本相對距離δ和局部密度ρ的決策圖選擇簇心;獲取簇心后,將剩余樣本點(diǎn)采用最近原則將其分配到更高密度的最近鄰類簇中,一步分配,快速簡潔.

但CFSFDP算法具有如下缺陷:

1)該算法采用小于截?cái)嗑嚯x樣本的個(gè)數(shù)作為樣本點(diǎn)密度,對于擁有相同密度即具有相同小于截?cái)嗑嚯x的樣本個(gè)數(shù)的節(jié)點(diǎn)而言,無法更加細(xì)致地區(qū)分2個(gè)節(jié)點(diǎn)誰更加稠密,從而對后期結(jié)合決策圖選取簇心造成一定干擾;

2)對于其高效的一步分配策略,會(huì)出現(xiàn)“多米諾骨牌效應(yīng)”,即:一旦某個(gè)數(shù)據(jù)點(diǎn)分配錯(cuò)誤,會(huì)影響剩余數(shù)據(jù)點(diǎn)的分配,現(xiàn)有的研究所提出的分配策略本質(zhì)上都是基于歐式距離計(jì)算而來的密度值進(jìn)行最近鄰原則分配雖然取得一定的效果,但并沒有從本質(zhì)上挖掘出樣本點(diǎn)間的相關(guān)性,造成樣本分配錯(cuò)誤,出現(xiàn)“多米諾骨牌效應(yīng)”.

3 可拓關(guān)聯(lián)函數(shù)改進(jìn)的密度峰值聚類算法

為有效處理CFSFDP算法中存在的兩個(gè)缺陷,本文將從密度度量方式和分配策略對其進(jìn)行改進(jìn).

1)引入節(jié)點(diǎn)平均差異度[27]概念衡量樣本密度,對各樣本點(diǎn)的密度更加細(xì)致的進(jìn)行區(qū)分,便于更加準(zhǔn)確的對簇心進(jìn)行選擇;

2)引入可拓關(guān)聯(lián)函數(shù)充分考慮樣本點(diǎn)與簇心之間相關(guān)性,用以揭示樣本點(diǎn)的類屬關(guān)系,提高樣本點(diǎn)分配的正確率,從而解決CFSFDP算法的“多米諾骨牌效應(yīng)”問題.在闡述本文算法之前,需先對節(jié)點(diǎn)局部平均差異度、可拓關(guān)聯(lián)函數(shù)的節(jié)域和經(jīng)典域進(jìn)行相關(guān)定義.

3.1 相關(guān)定義

為便于表述,首先定義樣本物元模型、簇心ζ的k距離、簇心ζ的k距離鄰域、樣本集節(jié)域和簇心ζ的k距離鄰域的經(jīng)典域等概念.對于樣本集O={O1,O2,…,On},其中Oi為m維向量(i=1,2,…,n),有如下定義:

定義1.節(jié)點(diǎn)局部平均差異度,即密度:

(8)

定義2.樣本物元模型:樣本Oi表示為:

(9)

其中C為樣本Oi的屬性特征,C=[c1,c2,…,cn],V為樣本Oi屬性特征所對應(yīng)的值,V=[v1,v2,…,vn].

定義3.簇心ξ的k距離:

簇心點(diǎn)ξ的k距離是ξ到它的k最近鄰的最大距離,記為k_dist(ζ).

(10)

其中Q(ζ)為簇心點(diǎn)ζ到它k最近鄰樣本點(diǎn)的集合,k的值不能過大,影響聚類正確率,也不能過小,增加算法運(yùn)行時(shí)間,一般取值為簇心個(gè)數(shù)的2～4倍.

定義4.簇心ζ的k距離鄰域:與簇心ζ距離小于k_dist(ζ)的樣本點(diǎn)集合,記為N(ζ)

定義5.樣本集節(jié)域:

(11)

為該樣本集O第j維屬性值的取值范圍,即為各屬性的節(jié)域.

定義6.簇心ζ的k距離鄰域的經(jīng)典域:

(12)

為第i個(gè)簇心ζi的k距離鄰域N(ζi)第j維屬性的取值范圍,即為各屬性的經(jīng)典域.

3.2 算法基本思想

本文提出的算法首先基于各節(jié)點(diǎn)平均局部差異度及距離繪制決策圖快速找到簇心,之后基于RDCA算法[12]中k距離鄰域思想,提出基于簇心點(diǎn)的k距離鄰域,得到各簇心的雛形簇心類;最后融合可拓關(guān)聯(lián)函數(shù)對各雛形簇心類不斷外擴(kuò),從而完成最終的聚類.

圖1 密度展示結(jié)構(gòu)圖Fig.1 Picture of density display

如圖1所示,以樣本點(diǎn)14,4,16為例,分別畫出以該點(diǎn)為圓心,以截?cái)嗑嚯xdc為半徑的圓,可看出在圓內(nèi),樣本數(shù)都為4個(gè),傳統(tǒng)的CFSFDP算法將其個(gè)數(shù)作為樣本點(diǎn)密度,即樣本點(diǎn)14,4,16密度相等,但圖中可看出,雖然樣本數(shù)相等,但各圓內(nèi)樣本與圓心的疏密程度是有所區(qū)別的,故本文提出的算法引入節(jié)點(diǎn)平均局部差異度概念描述樣本點(diǎn)的密度,對樣本點(diǎn)密度進(jìn)行更細(xì)致的描述;進(jìn)而利用決策圖找出簇心.

圖2 分配策略思想結(jié)構(gòu)圖Fig.2 Figure of distribution strategy

獲取簇心后,進(jìn)行樣本的分配,本文采用的分配策略實(shí)際是在聚類算法中引入分類的思想,基于可拓關(guān)聯(lián)函數(shù)對樣本點(diǎn)類簇歸屬情況給出相應(yīng)的分配策略如圖2所示,提高樣本點(diǎn)聚類的準(zhǔn)確性,從而降低CFSFDP算法“多米諾骨牌效應(yīng)”對聚類效果的不利影響.

根據(jù)改進(jìn)后的決策圖選出簇心,如圖2(a)中所示,點(diǎn)14,16,4為決策圖選出的3個(gè)簇心,將除簇心外的其他點(diǎn)都標(biāo)記為未分配點(diǎn);根據(jù)簇心的k距離鄰域,得到各雛形簇心類,如圖2(b)中虛線圓所示,并將樣本點(diǎn)1,6,12,5,18,20,2,7,11標(biāo)記為已分配點(diǎn);如圖2(c)中,在未分配點(diǎn)中隨機(jī)挑出一個(gè)樣本點(diǎn)13分別計(jì)算樣本點(diǎn)13與各雛形簇心類的關(guān)聯(lián)函數(shù)值,即相關(guān)度值,根據(jù)相關(guān)度值將樣本13分配到相關(guān)度大的簇類中,并將其標(biāo)記為已分配點(diǎn);依次判斷剩余未分配點(diǎn),如圖2(d)所示,直至完成所有未分配點(diǎn)的分配,即樣本點(diǎn)聚類完成.

3.3 算法的實(shí)施步驟

Step 1.根據(jù)公式(8)和公式(7)計(jì)算各樣本的局部平均差異度ρ和相對距離δ;

Step 2.根據(jù)ρ和δ值,繪制出樣本點(diǎn)的決策圖,從而確定簇心ζ;

Step 3.根據(jù)定義3中的公式(10)與定義4分別計(jì)算出各簇心ζi的k距離k_dist(ζi)及k距離鄰域N(ζi);

Step 4.將k距離領(lǐng)域N(ζi)默認(rèn)分配到各自的對應(yīng)的ζi簇心類cluster(i)中,并將其標(biāo)記為已分配點(diǎn),剩余點(diǎn)標(biāo)記為未分配點(diǎn);根據(jù)定義5中公式(11)計(jì)算出樣本集各屬性的節(jié)域vcj;

第三，某些選修課程設(shè)置的初期忽視了學(xué)生的呼聲和意見。某些選修課程的設(shè)置不但要圍繞某種理念進(jìn)行，對學(xué)生的興趣也要加以兼顧，以利于提高學(xué)生的學(xué)習(xí)興趣。

Step 5.從簇心集ζ中隨機(jī)取出一個(gè)未被訪問的簇心ζi,并將標(biāo)ζi記為已訪問點(diǎn).

圖3 算法流程結(jié)構(gòu)圖Fig.3 Algorithm flowchart

Step 6.根據(jù)定義6中公式(12)計(jì)算出雛形ζi簇心類cluster(i)樣本各屬性的經(jīng)典域vq,j,并根據(jù)公式(1-3)建立未分配點(diǎn)各屬性的關(guān)聯(lián)函數(shù),獲得對應(yīng)相關(guān)度值.

Step 7.根據(jù)信息熵[28]計(jì)算出各屬性權(quán)值,由公式(3)和公式(4)建立未分配點(diǎn)綜合關(guān)聯(lián)函數(shù),獲得各未分配點(diǎn)關(guān)于雛形ζi簇心類cluster(i)的綜合相關(guān)度值;

Step 8.若ζ中仍存在未訪問簇心點(diǎn),則返回到Step 5,直至ζ中所有簇心被訪問,則進(jìn)入下一步;

Step 9.將未分配點(diǎn)分配到綜合相關(guān)度值大的簇心類,完成未分配樣本點(diǎn)的聚類.

該算法流程如圖3所示.

3.4 算法復(fù)雜度分析

4 實(shí)驗(yàn)驗(yàn)證與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集和評價(jià)指標(biāo)

本文改進(jìn)的算法,通過Python語言編寫,用Spyder工具對實(shí)驗(yàn)結(jié)果進(jìn)行顯示.為了驗(yàn)證算法的有效性,本文選取4組人造數(shù)據(jù)和7組不同UCI數(shù)據(jù)庫數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),通過與CFSFDP算法、文獻(xiàn)[14]改進(jìn)過的IDPCA算法、DBSCAN算法和K-means算法進(jìn)行對比,以驗(yàn)證本文算法的性能.各數(shù)據(jù)的特征如表1所示,其中,Aggregation、Jain和Three cluster是人造數(shù)據(jù);Iris,Wine,Seeds,Ionosphere,WDBC,waveform3和CMC是UCI數(shù)據(jù)庫中的真實(shí)數(shù)據(jù).

聚類效果的衡量標(biāo)準(zhǔn),分為可視化衡量和定量衡量兩種,其中可視化衡量方法可以清晰明了的體現(xiàn)聚類結(jié)果和樣本的分布;定量衡量指標(biāo)采用聚類準(zhǔn)確率[29]指標(biāo)(Accuracy,ACC)作為聚類算法性能度量標(biāo)準(zhǔn).ACC取值范圍為[0,1],指標(biāo)值越大,表明聚類質(zhì)量越高.

表1 各數(shù)據(jù)集的基本特征
Table 1 Characteristics of the data set

數(shù)據(jù)集樣本個(gè)數(shù)樣本維數(shù)分類數(shù)Aggregation78827Jain37323Three cluster60023Data1150023Iris15043Wine179133Seeds21073Ionosphere351342WDBC569302Waveform35000213CMC147393

4.2 改進(jìn)的密度峰值聚類算法性能分析

4.2.1 可視化數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)采用4組數(shù)據(jù)集做可視化展示:Aggregation、Jain、Three cluster和Data1,其中Aggregation數(shù)據(jù)集簇間密度相對均勻,形狀多樣且簇與簇之間有連接;Jain數(shù)據(jù)集非線性分布,密度差異較大;Three cluster數(shù)據(jù)集形狀相似,各簇樣本密度相對均勻,簇間無交集;Data1數(shù)據(jù)集線性分布,疏密差異不大.

圖4-圖7是4組數(shù)據(jù)集分別基于這5種算法聚類得到的結(jié)果:圖4,圖5分別是基于Aggregation數(shù)據(jù)集與Three cluster數(shù)據(jù)集聚類的結(jié)果,其中圖4(d)IDPCA算法聚類效果最好,其次是圖4(b)本文算法,聚類效果最差的是圖4(f)K-means算法,而在圖5中聚類效果最好的是圖5(f)K-means算法,主要原因在于K-means算法對簇型數(shù)據(jù)集且各簇間彼此不相連的數(shù)據(jù)集聚類效果較好,其次是圖5(b)本文算法聚類效,表明本文算法對簇型且各簇有相連的數(shù)據(jù)集聚類效果較好.

圖6,圖7分別是基于Jain數(shù)據(jù)集與Data1數(shù)據(jù)集聚類的結(jié)果,圖6中圖6(b)本文算法聚類效果最好,其次是圖6(d)IDPCA算法和圖6(e)DBSCAN算法,最差的是圖6(c)CFSFDP算法與圖6(f)K-means算法,原因在于CFSFDP算法對樣本疏密度較為敏感,K-means算法對非簇型聚類效果不好;圖7中圖7(d)IDPCA算法聚類效果最好,其次是圖7(b)本文算法和圖7(e)DBSCA算法,最差的是圖7(f)K-means算法,表明本文算法對不同疏密與非線性數(shù)據(jù)集具有較好的聚類效果.

圖4 Aggregation數(shù)據(jù)集聚類Fig.4 Aggregation dataset cluster

圖5 Three cluster數(shù)據(jù)集聚類Fig.5 Three cluster dataset cluster

圖6 Jain數(shù)據(jù)集聚類Fig.6 Jain dataset cluster

圖7 Data1數(shù)據(jù)集聚類Fig.7 Data1 dataset cluster

其中,圖(a)為實(shí)際聚類結(jié)果,圖(b)為本文算法聚類結(jié)果,圖(c)為CFSFDP算法聚類結(jié)果,圖(d)為IDPCA算法聚類結(jié)果,圖(e)為DBSCAN算法聚類結(jié)果,圖(f)為K-means聚類結(jié)果.

圖8是5種算法聚類準(zhǔn)確率對比圖,從圖中可看出Aggregation和Three cluster數(shù)據(jù)集整體聚類結(jié)果偏好,聚類準(zhǔn)確率浮動(dòng)不大;從非線性和線性且密度有差異的兩組數(shù)據(jù)集Jain和Data1中可看出,本文算法對密度差異大的線性和非線性數(shù)據(jù)聚類效果更好,其次是IDPCA算法,CFSFDP算法和K-means算法聚類效果相對較差.

圖8 該5種算法聚類準(zhǔn)確率對比圖Fig.8 Clustering accuracy ratio comparison chart

其中,x軸坐標(biāo)中0:樣本真實(shí)分布;2:本文算法;4:CFSFDP算法;6:IDPCA算法;8:DBSCAN算法;10:K-means算法.

4.2.2 非可視化數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

為了進(jìn)一步驗(yàn)證本文算法的有效性,選取7組來自UCI數(shù)據(jù)庫的實(shí)驗(yàn)數(shù)據(jù)集Iris,Wine,Seeds,Ionosphere,WDBC,waveform3和CMC數(shù)來測試,這7組數(shù)據(jù)都有明確的分類標(biāo)簽,因此可以用來對比驗(yàn)證聚類結(jié)果的好壞及算法的性能.

表2為各算法基于Iris,Wine,Seeds,Ionosphere,WDBC,waveform3和CMC 7個(gè)真實(shí)數(shù)據(jù)集聚類后的ACC評價(jià)指標(biāo)值.

表2 7個(gè)數(shù)據(jù)集聚類后的ACC指標(biāo)
Table 2 ACC indicator after clustering of data sets

數(shù)據(jù)集本文算法CFSFDPIDPCADBSCANKmeansIris0.9690.94—0.7930.78Wine0.9100.8830.8960.6650.7Seeds0.9470.8950.9380.7150.89Iono-sphere0.7880.6810.7690.6070.712WDBC0.9630.6130.9490.8700.928Waveform30.6980.5860.665—0.501CMC0.6750.65—0.560.35

從表2中可得出本文算法在聚類準(zhǔn)確率上整體優(yōu)于其他4種算法,尤其對高維度的數(shù)據(jù)集Ionosphere,WDBC,Waveform3聚類優(yōu)勢更明顯.通過5種算法對UCI真實(shí)數(shù)據(jù)集的聚類準(zhǔn)確性的對比分析可以發(fā)現(xiàn),本文提出的算法具有良好的聚類性能,優(yōu)于CFSFDP算法、IDPCA算法、DBSCAN算法和K-means算法.

5 總 結(jié)

本文針對由于CFSFDP算法聚類準(zhǔn)確率低的問題,提出一種融合可拓關(guān)聯(lián)函數(shù)的密度峰值聚類算法.采用平均差異度作為樣本密度衡量指標(biāo),借鑒CFSFDP算法決策圖選取簇心;從簇心出發(fā)引入k鄰域及關(guān)聯(lián)函數(shù)思想對未分配點(diǎn)完成準(zhǔn)確聚類.該算法在不同類型數(shù)據(jù)集上的實(shí)驗(yàn),證明了本文提出的算法對任意形狀,任意密度的數(shù)據(jù)集的聚類效果和聚類準(zhǔn)確性均優(yōu)于經(jīng)典的CFSFDP算法、DBSCAN算法、K-means算法及改進(jìn)的IDPCA算法.但本文算法中k鄰域的參數(shù)k的取值是憑經(jīng)驗(yàn)選取,如何實(shí)現(xiàn)針對不同數(shù)量及不同維度的數(shù)據(jù)集自動(dòng)選取最優(yōu)k值是今后研究的方向.