一種基于密度峰值的針對模糊混合數據的聚類算法*

陳奕延 ，李 曄,李存金

(1.北京理工大學管理與經濟學院，北京 100081;2.中國管理科學研究院學術委員會,北京 100036; 3.中國社會科學院大學(研究生院)，北京 102488)

1 引言

聚類分析是按照某個特定標準把數據對象劃分成子集的過程，每個子集表示一個簇。聚類分析是一種無監督學習過程，其目的是使得簇中的對象彼此相似，但與其它簇對象不相似[1,2]。目前，聚類分析廣泛應用于商務智能、生物安全、Web檢索、評價與決策等領域。按照陳彩棠[3]的觀點，聚類分析算法可以分為6類，包括基于劃分[4 - 6]、層次[7 - 9]、密度[10]、網格[11,12]、概率模型[13]以及基于約束[14]的聚類算法。這種劃分方式并不一定涵蓋所有的聚類算法，譬如基于圖論[15]的聚類算法，但不論何種算法皆有其各自的特點。

2 相關工作

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

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

因此，本文在模糊集理論的基礎上，提出了針對由連續型模糊集與離散型模糊集組成的模糊混合數據的聚類算法FMD-CFSFDP(Fuzzy Mixed Data-Clustering algorithm by Fast Search and Find of Density Peaks)。該算法可滿足含有模糊混合數據的樣本的聚類需求，繼承了CFSFDP算法的優點，并且具備3項創新：

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

(2)利用連續型模糊集和離散型模糊集，構建了模糊集上針對模糊混合數據的聚類算法；

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

3 模糊混合數據的數學定義

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

4 FMD-CFSFDP算法步驟

4.1 計算聚類的度量

(1)

(2)

(3)

(4)

或

(5)

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

(6)

(7)

(8)

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

(9)

4.2 其余聚類步驟

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

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

5 隨機模擬實驗

(10)

其中，K表示該樣本集真實的簇的個數,corr_ci表示第i個簇中被正確聚類的模糊樣本個數,|D|為模糊樣本個數。corr_ci越大，則說明聚類效果越好。計算第1組隨機模擬實驗的聚類正確率和最優閾值L*,如表1所示。平均聚類正確率MC=63.38%，聚類正確率的標準差SD=6.3628。

Table 1 25 results of the 1st random simulation 表1 第1組隨機模擬25次的實驗結果

Figure 2 Clustering effect diagram of the 17th experiment in the 1st random simulation圖2 第1組第17次實驗的聚類效果圖

Table 2 25 results of the 2nd random simulation 表2 第2組隨機模擬25次實驗結果

Figure 3 Clustering effect diagram of the 6th experiment of the 2nd random simulation圖3 第2組第6次實驗的聚類效果圖

顯然，從彩圖[29]可以看出，代表3個簇的彩色團塊中夾雜著不同的顏色，說明第2組的聚類的效果不如第1組第17次實驗理想。另外，將表1與表2中的聚類正確率與參考文獻[16，20]比較，顯然可以發現FMD-CFSFDP算法的聚類正確率沒有CFSFDP和MAO-CFSFDP的高。這是因為樣本每一個指標下的模糊集中對應的每種狀態(元素)都被當成數值參與運算，對于任意連續型模糊集而言則均有無數個元素參與運算，故聚類正確率會較前2者偏低。分別畫出第1組隨機模擬中第17次實驗，以及第2組隨機模擬中第6次實驗下γ值降序排列后的決策圖，如圖4所示，由于非簇中心的γ會比較平滑，故可以利用跳躍點判斷簇中心個數，γ值的計算和含義沿用CFSFDP算法。

Figure 4 The descending γ decision diagram in two different experiments圖4 2次不同實驗的降序γ值決策圖

由γ的情況以及聚類結果可知，第1組模擬的第17次實驗中，人工劃分的簇數是2個，根據圖4a中所示，其擁有2個跳躍點，故自動識別出的簇數也是2個；而第2組模擬的第6次實驗中，人工劃分的簇數是3個，但從圖4b中可以看出，其自動識別出的簇數為6。顯然，FMD-CFSFDP算法利用γ值的跳躍點來自動識別簇數是不穩定的。因為不論連續型模糊集還是離散型模糊集，計算其相應的改進型歐氏距離中使用的隸屬度的取值是在[0,1]，因此算出的改進型歐氏距離較小，導致整體距離L、最優閾值L*、密度ρ、特殊距離δ與綜合考量值γ也較小，反映在圖像中的區分度較低，因此單純通過視覺識別γ值跳躍點就變得比較困難。

6 結束語

FMD-CFSFDP算法可滿足模糊混合數據的聚類需求，在模糊集上繼承了CFSFDP算法的大多數優點，本文的主要創新之處在于FMD-CFSFDP算法把CFSFDP算法從經典集擴展到了模糊集上，同時也吸收了MAO-CFSFDP算法的優勢，賦予“模糊混合數據”數學涵義，改進了作為度量的傳統模糊歐氏距離，使改進后的改進型歐氏距離具有更小的誤差，可以提高聚類精度。

然而，縱有上述創新，FMD-CFSFDP算法仍存在以下3個缺點：

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

(2)雖然使用了誤差較傳統歐氏距離更小的改進型歐氏距離，并利用權值對其進行了加權處理，從而得到整體距離，但由于其權值是固定的，無法自適應調整，這無疑會削弱整體距離的區分度，從而導致聚類正確率相比CFSFDP算法有所下降。

(3)FMD-CFSFDP算法未能解決CFSFDP算法中利用視覺識別跳躍點尋找簇數的方法的缺陷，這在一定程度上是由于度量的計算使用了隸屬度，從而導致最后綜合考量值的區分度過低，無法利用視覺有效地尋找跳躍點。

針對上述缺點，未來可對FMD-CFSFDP算法做如下拓展改進：

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

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

(3)放棄利用視覺識別幾何圖像中γ值的特征尋找簇數的方式，可以研究一套量化的數學模型來自動尋找簇的個數，這樣即便發生前述缺點(2)和(3)中的情況，微小的差異也可以被數學模型輕易識別出來，從而提高了聚類的區分度。

綜上，FMD-CFSFDP算法雖然存在不足之處，但它的提出可為進一步研究模糊集上的聚類算法提供參考。