一種基于密度峰值的針對(duì)模糊混合數(shù)據(jù)的聚類(lèi)算法*

陳奕延 ，李 曄,李存金

(1.北京理工大學(xué)管理與經(jīng)濟(jì)學(xué)院，北京 100081;2.中國(guó)管理科學(xué)研究院學(xué)術(shù)委員會(huì),北京 100036; 3.中國(guó)社會(huì)科學(xué)院大學(xué)(研究生院)，北京 102488)

1 引言

聚類(lèi)分析是按照某個(gè)特定標(biāo)準(zhǔn)把數(shù)據(jù)對(duì)象劃分成子集的過(guò)程，每個(gè)子集表示一個(gè)簇。聚類(lèi)分析是一種無(wú)監(jiān)督學(xué)習(xí)過(guò)程，其目的是使得簇中的對(duì)象彼此相似，但與其它簇對(duì)象不相似[1,2]。目前，聚類(lèi)分析廣泛應(yīng)用于商務(wù)智能、生物安全、Web檢索、評(píng)價(jià)與決策等領(lǐng)域。按照陳彩棠[3]的觀點(diǎn)，聚類(lèi)分析算法可以分為6類(lèi)，包括基于劃分[4 - 6]、層次[7 - 9]、密度[10]、網(wǎng)格[11,12]、概率模型[13]以及基于約束[14]的聚類(lèi)算法。這種劃分方式并不一定涵蓋所有的聚類(lèi)算法，譬如基于圖論[15]的聚類(lèi)算法，但不論何種算法皆有其各自的特點(diǎn)。

2 相關(guān)工作

Rodriguez等[16]于2014年提出了快速搜索和發(fā)現(xiàn)密度峰值的聚類(lèi)CFSFDP(Clustering by Fast Search and Find of Density Peaks)算法，這是一種基于密度、可自動(dòng)獲得簇的正確個(gè)數(shù)，并能夠解決數(shù)據(jù)空間分布呈非球形簇的聚類(lèi)算法。許多學(xué)者在CFSFDP算法的基礎(chǔ)上進(jìn)行了改進(jìn)：Wan等[17]對(duì)CFSFDP算法中尋找簇中心的決策圖方法提出了質(zhì)疑，提出了一種Fuzzy CFSFDP算法，并利用基于流形距離和基于標(biāo)準(zhǔn)差的截?cái)嗑嚯x對(duì)其進(jìn)行優(yōu)化；Zhang等[18]在無(wú)線傳感網(wǎng)絡(luò)中將CFSFDP算法與層次協(xié)議相結(jié)合，提出了一種考慮剩余能量的改進(jìn)型CFSFDP-E算法；Qin等[19]把太赫茲時(shí)域光譜與CFSFDP算法結(jié)合，提出了PCA-CFSFDP算法；李曄等[20]提出了針對(duì)混合型數(shù)據(jù)集的MAO-CFSFDP算法，并使用該算法解決了實(shí)際問(wèn)題[21]，從而驗(yàn)證了該算法的可靠性。

雖然MAO-CFSFDP算法拓展了數(shù)據(jù)類(lèi)型，但它與CFSFDP算法及其它改進(jìn)算法都是建立在經(jīng)典集合上的聚類(lèi)算法，而現(xiàn)實(shí)生活中的許多對(duì)象是不具備嚴(yán)格屬性的，無(wú)法用“非此即彼”的二值邏輯解釋，參考Zadeh[22]提出的模糊集理論，這些對(duì)象是具有模糊概念的事物。目前常用的PCM[23]、FCM[24]、PFCM[25]等算法依賴統(tǒng)計(jì)不確定性理論(概率分布、貝葉斯模型等)，將聚類(lèi)對(duì)象與簇之間的隸屬關(guān)系不確定化，但仍定義在經(jīng)典集合上，無(wú)法解決模糊數(shù)據(jù)的距離問(wèn)題。

因此，本文在模糊集理論的基礎(chǔ)上，提出了針對(duì)由連續(xù)型模糊集與離散型模糊集組成的模糊混合數(shù)據(jù)的聚類(lèi)算法FMD-CFSFDP(Fuzzy Mixed Data-Clustering algorithm by Fast Search and Find of Density Peaks)。該算法可滿足含有模糊混合數(shù)據(jù)的樣本的聚類(lèi)需求，繼承了CFSFDP算法的優(yōu)點(diǎn)，并且具備3項(xiàng)創(chuàng)新：

(1)從理論上將CFSFDP算法從經(jīng)典集擴(kuò)展到了模糊集上，提出模糊混合數(shù)據(jù)的概念；

(2)利用連續(xù)型模糊集和離散型模糊集，構(gòu)建了模糊集上針對(duì)模糊混合數(shù)據(jù)的聚類(lèi)算法；

(3)改進(jìn)了模糊集上的傳統(tǒng)歐氏距離，分別定義了模糊集上針對(duì)連續(xù)型模糊集和離散型模糊集的改進(jìn)型歐氏距離，使之相較前者誤差減少，令聚類(lèi)的度量更為合理。

3 模糊混合數(shù)據(jù)的數(shù)學(xué)定義

記連續(xù)型模糊集為連續(xù)型模糊數(shù)據(jù)，離散型模糊集為離散型模糊數(shù)據(jù)，假設(shè)存在數(shù)據(jù)集Θ，若Θ中存在N1個(gè)連續(xù)型模糊數(shù)據(jù)組成的數(shù)據(jù)子集Θ1，以及N2個(gè)離散型模糊數(shù)據(jù)組成的數(shù)據(jù)子集Θ2，滿足：Θ1∩Θ2=?，Θ1∪Θ2=Θ，則稱數(shù)據(jù)集Θ為模糊混合數(shù)據(jù)集，簡(jiǎn)稱模糊混合數(shù)據(jù)。模糊混合數(shù)據(jù)是由數(shù)據(jù)形式為連續(xù)型模糊數(shù)據(jù)(連續(xù)型模糊集)與離散型模糊數(shù)據(jù)(離散型模糊集)混合組成的數(shù)據(jù)集。

4 FMD-CFSFDP算法步驟

4.1 計(jì)算聚類(lèi)的度量

(1)

(2)

(3)

(4)

或

(5)

則式(1)的系統(tǒng)誤差為：

(6)

(7)

(8)

L(r,t)=LC(r,t)+LD(r,t)

(9)

4.2 其余聚類(lèi)步驟

Figure 1 Flow chart of FMD-CFSFDP algorithm圖1 FMD-CFSFDP算法流程圖

FMD-CFSFDP算法是順序結(jié)構(gòu)，所以其最大時(shí)間復(fù)雜度是O(N·M2)，而CFSFDP算法的復(fù)雜度是O(M2)[27]，顯然，由于數(shù)據(jù)形式和度量都變得復(fù)雜，所以FMD-CFSFDP算法的復(fù)雜度要高于CFSFDP算法的。

5 隨機(jī)模擬實(shí)驗(yàn)

(10)

其中，K表示該樣本集真實(shí)的簇的個(gè)數(shù),corr_ci表示第i個(gè)簇中被正確聚類(lèi)的模糊樣本個(gè)數(shù),|D|為模糊樣本個(gè)數(shù)。corr_ci越大，則說(shuō)明聚類(lèi)效果越好。計(jì)算第1組隨機(jī)模擬實(shí)驗(yàn)的聚類(lèi)正確率和最優(yōu)閾值L*,如表1所示。平均聚類(lèi)正確率MC=63.38%，聚類(lèi)正確率的標(biāo)準(zhǔn)差SD=6.3628。

Table 1 25 results of the 1st random simulation 表1 第1組隨機(jī)模擬25次的實(shí)驗(yàn)結(jié)果

Figure 2 Clustering effect diagram of the 17th experiment in the 1st random simulation圖2 第1組第17次實(shí)驗(yàn)的聚類(lèi)效果圖

Table 2 25 results of the 2nd random simulation 表2 第2組隨機(jī)模擬25次實(shí)驗(yàn)結(jié)果

Figure 3 Clustering effect diagram of the 6th experiment of the 2nd random simulation圖3 第2組第6次實(shí)驗(yàn)的聚類(lèi)效果圖

顯然，從彩圖[29]可以看出，代表3個(gè)簇的彩色團(tuán)塊中夾雜著不同的顏色，說(shuō)明第2組的聚類(lèi)的效果不如第1組第17次實(shí)驗(yàn)理想。另外，將表1與表2中的聚類(lèi)正確率與參考文獻(xiàn)[16，20]比較，顯然可以發(fā)現(xiàn)FMD-CFSFDP算法的聚類(lèi)正確率沒(méi)有CFSFDP和MAO-CFSFDP的高。這是因?yàn)闃颖久恳粋€(gè)指標(biāo)下的模糊集中對(duì)應(yīng)的每種狀態(tài)(元素)都被當(dāng)成數(shù)值參與運(yùn)算，對(duì)于任意連續(xù)型模糊集而言則均有無(wú)數(shù)個(gè)元素參與運(yùn)算，故聚類(lèi)正確率會(huì)較前2者偏低。分別畫(huà)出第1組隨機(jī)模擬中第17次實(shí)驗(yàn)，以及第2組隨機(jī)模擬中第6次實(shí)驗(yàn)下γ值降序排列后的決策圖，如圖4所示，由于非簇中心的γ會(huì)比較平滑，故可以利用跳躍點(diǎn)判斷簇中心個(gè)數(shù)，γ值的計(jì)算和含義沿用CFSFDP算法。

Figure 4 The descending γ decision diagram in two different experiments圖4 2次不同實(shí)驗(yàn)的降序γ值決策圖

由γ的情況以及聚類(lèi)結(jié)果可知，第1組模擬的第17次實(shí)驗(yàn)中，人工劃分的簇?cái)?shù)是2個(gè)，根據(jù)圖4a中所示，其擁有2個(gè)跳躍點(diǎn)，故自動(dòng)識(shí)別出的簇?cái)?shù)也是2個(gè)；而第2組模擬的第6次實(shí)驗(yàn)中，人工劃分的簇?cái)?shù)是3個(gè)，但從圖4b中可以看出，其自動(dòng)識(shí)別出的簇?cái)?shù)為6。顯然，F(xiàn)MD-CFSFDP算法利用γ值的跳躍點(diǎn)來(lái)自動(dòng)識(shí)別簇?cái)?shù)是不穩(wěn)定的。因?yàn)椴徽撨B續(xù)型模糊集還是離散型模糊集，計(jì)算其相應(yīng)的改進(jìn)型歐氏距離中使用的隸屬度的取值是在[0,1]，因此算出的改進(jìn)型歐氏距離較小，導(dǎo)致整體距離L、最優(yōu)閾值L*、密度ρ、特殊距離δ與綜合考量值γ也較小，反映在圖像中的區(qū)分度較低，因此單純通過(guò)視覺(jué)識(shí)別γ值跳躍點(diǎn)就變得比較困難。

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

FMD-CFSFDP算法可滿足模糊混合數(shù)據(jù)的聚類(lèi)需求，在模糊集上繼承了CFSFDP算法的大多數(shù)優(yōu)點(diǎn)，本文的主要?jiǎng)?chuàng)新之處在于FMD-CFSFDP算法把CFSFDP算法從經(jīng)典集擴(kuò)展到了模糊集上，同時(shí)也吸收了MAO-CFSFDP算法的優(yōu)勢(shì)，賦予“模糊混合數(shù)據(jù)”數(shù)學(xué)涵義，改進(jìn)了作為度量的傳統(tǒng)模糊歐氏距離，使改進(jìn)后的改進(jìn)型歐氏距離具有更小的誤差，可以提高聚類(lèi)精度。

然而，縱有上述創(chuàng)新，F(xiàn)MD-CFSFDP算法仍存在以下3個(gè)缺點(diǎn)：

(1)FMD-CFSFDP算法中的模糊樣本涵蓋的信息是模糊集，但模糊樣本與簇之間的隸屬關(guān)系依然使用了硬劃分而未能考慮模糊的特性，雖然模糊數(shù)學(xué)上的許多計(jì)算，包括模糊貼近度、模糊度、模糊距離等都是把模糊量轉(zhuǎn)化為經(jīng)典量，最終計(jì)算結(jié)果也都是經(jīng)典數(shù)值，這在模糊數(shù)學(xué)上是合理的。但是，從模糊集到經(jīng)典集的轉(zhuǎn)化過(guò)程中往往會(huì)損失一些信息，特別是對(duì)于模糊樣本的劃分，如果采用硬劃分則會(huì)造成聚類(lèi)正確率在一定程度上的下降。

(2)雖然使用了誤差較傳統(tǒng)歐氏距離更小的改進(jìn)型歐氏距離，并利用權(quán)值對(duì)其進(jìn)行了加權(quán)處理，從而得到整體距離，但由于其權(quán)值是固定的，無(wú)法自適應(yīng)調(diào)整，這無(wú)疑會(huì)削弱整體距離的區(qū)分度，從而導(dǎo)致聚類(lèi)正確率相比CFSFDP算法有所下降。

(3)FMD-CFSFDP算法未能解決CFSFDP算法中利用視覺(jué)識(shí)別跳躍點(diǎn)尋找簇?cái)?shù)的方法的缺陷，這在一定程度上是由于度量的計(jì)算使用了隸屬度，從而導(dǎo)致最后綜合考量值的區(qū)分度過(guò)低，無(wú)法利用視覺(jué)有效地尋找跳躍點(diǎn)。

針對(duì)上述缺點(diǎn)，未來(lái)可對(duì)FMD-CFSFDP算法做如下拓展改進(jìn)：

(1)將模糊樣本與簇之間的隸屬關(guān)系也定義在模糊集上，從而使樣本信息和隸屬關(guān)系均建立在模糊集上，這或許可以減少聚類(lèi)劃分造成的信息損失，提高聚類(lèi)正確率；

(2)放棄使用隸屬度進(jìn)行計(jì)算的模糊距離及其相關(guān)一切改進(jìn)，尋找新的可以體現(xiàn)模糊數(shù)據(jù)屬性的計(jì)算公式作為度量；

(3)放棄利用視覺(jué)識(shí)別幾何圖像中γ值的特征尋找簇?cái)?shù)的方式，可以研究一套量化的數(shù)學(xué)模型來(lái)自動(dòng)尋找簇的個(gè)數(shù)，這樣即便發(fā)生前述缺點(diǎn)(2)和(3)中的情況，微小的差異也可以被數(shù)學(xué)模型輕易識(shí)別出來(lái)，從而提高了聚類(lèi)的區(qū)分度。

綜上，F(xiàn)MD-CFSFDP算法雖然存在不足之處，但它的提出可為進(jìn)一步研究模糊集上的聚類(lèi)算法提供參考。