結合FCS的多視圖模糊聚類算法

劉永利，郭呈怡，劉 靜，吳 巖

(河南理工大學 計算機科學與技術學院，河南 焦作 454000)

聚類技術能夠在無監督的條件下揭示出數據背后隱藏的知識和結構，故而在大數據的時代背景下備受關注。按照隸屬度取值范圍的不同，聚類技術可劃分為硬聚類和模糊聚類兩種。在硬聚類算法中，一個樣本只能完全隸屬于一個簇；模糊聚類則將隸屬度取值范圍從硬聚類的0和1二值擴展至實數區間[0,1]，即允許一個樣本以一定概率同時隸屬于多個簇?？紤]到樣本主題的多樣化特點，以模糊C均值聚類(Fuzzy C-Means, FCM)算法[1]為代表的模糊聚類算法在聚類準確率方面更具優勢。然而，該算法及其衍生算法對噪聲數據較為敏感，導致算法的有效性易受影響。為了提高算法的魯棒性，文獻[2]提出了模糊緊致性分離性聚類算法(Fuzzy Compactness and Separation, FCS)，該算法將類間距離作為懲罰項加入到目標函數中，實驗效果較為理想。文獻[3]提出了一種嵌入隱馬爾科夫隨機場的中智C聚類算法，并在此基礎上，引入核函數將歐式空間的樣本映射至高維空間，提出了核空間隱馬爾科夫隨機場的中智C聚類算法。

上述模糊聚類算法的聚類對象通常只具有單一表示或單一視圖。然而，現實世界的數據日臻復雜，多視圖的特點日漸突出，即從不同的角度觀察同一個樣本，觀察結果可能大相徑庭。多視圖數據具有多種表示，且不同表示之間可以相互補充。雖然從每一種表示出發都可以對數據進行聚類，但是結果比較片面；只有對數據的多種表示協同聚類，才能形成對數據的完整認識。

大多數多視圖聚類算法通過協同方式或正則化方式完成多視圖聚類任務，前者利用每個視圖的信息直接獲得一致聚類結果，后者則是減小每個視圖的聚類結果與一致聚類結果的差異。文獻[4-5]結合譜聚類算法，提出了基于協同的多視圖譜聚類算法和基于聯合正則化的多視圖譜聚類算法。文獻[6]提出了一種處理關系數據的多視圖模糊聚類算法，聚類過程中選取樣本作為每個簇的質心。文獻[7]提出了一種基于特征加權和非負矩陣分解的多視角聚類算法，該算法通過最小化每個視角的系數矩陣與一致矩陣的差異完成聚類目的。在非負矩陣分解過程中，往往忽視了樣本空間的局部結構，針對此問題，文獻[8]提出的一種基于非負矩陣分解的模糊聚類算法，引入了流型正則化項。文獻[9-10]基于K-Means算法和非負矩陣分解提出的兩種多視圖聚類算法，考慮了樣本的權重。文獻[11]提出了一種魯棒的多視圖均值聚類(Robust Multi-view K-Means Clustering, RMKMC)算法，可以有效處理大規模數據。文獻[12]提出一種多視圖模糊聚類算法，可以識別每個視圖的重要性。文獻[13]為了減小冗余特征對聚類結果的影響，提出了一種基于特征選擇的多視圖聚類算法。文獻[14]提出了一種基于模糊C均值聚類算法的極小化極大值優化算法(Minimax optimization based on Fuzzy C-Means, MinimaxFCM)，該算法使用極小化極大值算法降低高權重視圖的權重，達到各視圖間聚類結果的平衡。文獻[15]提出了使用粒子群優化雙權重的多視圖聚類算法，在每次迭代中通過粒子群優化尋找質心。上述多視圖聚類算法通過綜合數據的不同表示產生一致聚類結果，有助于提高聚類的準確率；然而，噪聲數據并未引起重視，因此，當噪聲出現時，這些算法在更新質心時易受干擾，進而影響聚類有效性。

基于以上分析，筆者提出了一種多視圖模糊緊致性分離性算法(Multi-view Fuzzy Compactness and Separation, MvFCS)，將模糊緊致性分離性算法應用到多視圖數據處理中，可以有效解決多視圖聚類問題。該算法根據各視圖的重要性為其賦予不同權重，對不同視圖協同聚類易于提高聚類的準確率；同時，繼承模糊緊致性分離性算法的魯棒性優勢，有助于降低噪聲對各質心的影響。

1 模糊緊致性分離性算法

鑒于模糊C均值聚類算法對于噪聲數據較為敏感，文獻[2]提出了模糊緊致性分離性算法，該算法同時考慮了類內緊致性和類間分離性，有助于增強算法的魯棒性。設數據集X包含N個樣本，X={x1,…,xN}，其特征維度為D，v1,…,vK為K個質心，用U表示K×N的隸屬度矩陣，V為質心矩陣，其目標函數及約束可分別表示為

(1)

(2)

(3)

其中，m為控制模糊程度的參數，uci表示第i個對象對第c個簇的隸屬度。式(1)分為兩項，第1項表示類內距離；第2項表示類間分離性，前取負號表示類間分離性對目標函數的貢獻呈負性；x為所有樣本中心；η為一個K維向量。在聚類過程中，模糊緊致性分離性算法兼顧類內距離和類間距離，即該算法通過減小類內距離和增大類間距離優化目標函數JFCS，有效降低了噪聲數據造成的影響。

為了實現多視圖數據聚類，并降低對噪聲數據的敏感程度，將模糊緊致性分離性算法與多視圖模糊聚類相結合，提出了多視圖模糊緊致性分離性算法。該算法為每個視圖賦予不同的權重，綜合各視圖的結果進行協同聚類。在聚類過程中，使用極小化極大值算法優化權重最高的視圖，從而實現各個視圖間隸屬度矩陣的一致性。

2 多視圖模糊緊致性分離性算法

2.1 算法的目標函數

對于有P個視圖和N個對象的多視圖數據集X={X(1),…,X(P)}，定義V={V(1),…,V(P)}，為多視圖數據集X的質心矩陣。算法的目標函數可表示為

(4)

其中，

(5)

(6)

(7)

(8)

算法通過優化如式(4)所示的目標函數，產生多視圖的聚類結果。在聚類過程中，首先利用視圖權重α(p)整合不同視圖的信息，然后用隸屬度矩陣U返回不同視圖一致的聚類結果。

2.2 算法的優化

在待求解變量中，ηc(p)的求解公式已經給出(如式(8)所示)，隸屬度矩陣U、質心矩陣V和權重向量α的表達式采用拉格朗日乘數法求解。構造的拉格朗日函數為

(9)

2.2.1 固定質心和權重并求解隸屬度

將質心和權重視為常量，隸屬度視為變量，對式(9)關于uci求偏導，并令偏導數等于0，可得

(10)

(11)

對于某一對象xi，如果存在一個質心vc使得

(12)

即式(11)的分子小于或者等于0，那么uci=1，且對任意的t(t∈{1,2,…,K},t≠c)，有uti=0。

2.2.2 固定權重和隸屬度并求解質心

將權重和隸屬度視為常量，質心視為變量，對式(9)關于vc(p)求偏導，并令偏導數等于0，可得

(13)

由式(13)可得到vc(p)的更新公式，即

(14)

2.2.3 固定質心和權重并求解隸屬度

將隸屬度和質心視為常量，權重向量α(p)視為變量，對式(9)關于α(p)求偏導，并令偏導數等于0，可得

(15)

由式(15)和式(7)可得到權重α(p)的更新公式為

(16)

在聚類過程中，對式(8)、(11)、(14)和(16)迭代更新，可得算法的聚類結果。

2.3 算法的步驟

算法與極小化極大值優化算法[14]的更新順序一致，即先初始化α和V，再更新η和U。

算法1多視圖模糊緊致性分離性算法。

輸入 多視圖數據集X={X(1),…,X(P)}，簇數目K，參數γ、m和β，最大迭代次數T，閾值參數ξ。

輸出 聚類結果向量q。

① 初始化每個視圖的質心矩陣V(p)，得到數據集X的質心矩陣V；

② 初始化權重向量α(p)=1/P；

③ 初始化當前迭代次數t=0；

repeat{

④ forp=1:P

⑤ forc=1:K

⑥ 利用式(8)更新ηc(p)；

⑦ end for

⑧ end for

⑨ forc=1:K

}until‖Ut+1-Ut║<ξ或者t>T

算法的時間復雜度主要取決于更新η、隸屬度矩陣、質心矩陣和視圖權重向量4部分，其中更新一次η的時間復雜度為O(PK2)，更新一次隸屬度矩陣、質心矩陣、視圖權重向量的時間復雜度均為O(PNK)，所以算法總的時間復雜度為O(t(3PNK+PK2))，t為迭代次數。

3 實驗分析

實驗的環境為操作系統Windows 7，CPU型號Inter i3-4150，頻率3.50GHz，內存4GB，編譯軟件為MATLAB R2016a。

實驗中參數的取值：K的值由聚類數目決定，參數m、γ和β需要在實驗中選取最優值，默認輸入m=1.5，γ=0.5，β=0.4，最大迭代次數T=1 000，閾值參數ξ=10-5。

在每個視圖中，隨機挑選K個樣本作為初始質心。為了保證實驗結果的有效性，對每個算法運行10次，取這10次運行結果的平均值作為算法的實驗結果。

3.1 實驗準備

為了驗證算法的有效性，選取4個多視圖數據集進行了實驗，各數據集的信息見表1。

為便于比較，實驗選取了3個對比算法，分別為模糊緊致性分離性算法(FCS)、魯棒的多視圖均值聚類算法(RMKMC)和極小化極大值優化算法(MinimaxFCM)。其中，模糊緊致性分離性算法為單視圖聚類算法，其他兩種算法為多視圖聚類算法。實驗過程首先用模糊緊致性分離性算法對每個視圖進行單獨聚類，得到每個視圖的聚類結果，記錄最差單視圖結果為FCS 1，記錄最好單視圖結果為FCS 2，然后將每個視圖的特征放到一起進行模糊緊致性分離性聚類，結果記為FCS。實驗結果使用準確率(Accuracy)、F度量(F-Measure)和標準化互信息(Normalized Mutual Znformation,NMI)這3個指標進行評價。

表1 多視圖數據集的詳細信息

為了評估多視圖模糊緊致性分離性算法的魯棒性，在原始數據集上完成聚類后，在每個數據集中添加10%～15%的噪聲數據，并再次比較各算法的聚類效果。各數據集上添加的噪聲樣本數如表1所示。

3.2 實驗結果

實驗數據包括未添加噪聲數據和添加噪聲數據兩部分，并據此組織兩組實驗。對于未添加噪聲數據的實驗，討論多視圖聚類算法和單視圖聚類算法的效果，并比較多視圖模糊緊致性分離性算法、魯棒的多視圖均值聚類算法和極小化極大值優化算法這3種多視圖聚類算法的性能；對于添加噪聲數據部分的實驗，則驗證算法的魯棒性。

IS、MF、MMKSD和Cal這4個數據集上的實驗結果分別如表2～表5所示，每個表包含了未添加噪聲數據和添加噪聲數據的兩部分實驗結果。

表2 在有無噪聲兩種情況下IS數據集上的準確率對比

表3 在有無噪聲兩種情況下MF數據集上的準確率對比

表4 在有無噪聲兩種情況下MMKSD數據集上的準確率對比

表5 在有無噪聲兩種情況下Cal數據集上的準確率對比

表2給出了IS數據集上的實驗結果。當未添加噪聲數據時，FCS 2的準確率為58.09%，FCS的準確率為60%，而3種多視圖聚類算法的最低準確率(魯棒的多視圖均值聚類算法)為62.38%，最高(多視圖模糊緊致性分離性算法)為66.19%。該結果說明，相較于單視圖算法，多視圖聚類算法通常可以獲得更高的聚類準確率；同時，相較于魯棒的多視圖均值聚類算法和極小化極大值優化算法這兩種多視圖聚類算法，多視圖模糊緊致性分離性算法可以更有效地完成聚類任務。當添加噪聲數據后，FCS算法展現出優秀的噪聲抵抗能力，多視圖模糊緊致性分離性算法繼承了模糊緊致性分離性算法的優點，準確率上升了0.47%，所受影響甚微，而魯棒的多視圖均值聚類算法的準確率下降了4.29%，極小化極大值優化算法的準確率下降了7.14%，這兩種算法受到的影響相對較大。各算法在MF、MMKSD和Cal數據集上也有相似表現。

從上述數據集的實驗結果可以得出兩個結論：①相較于單視圖聚類算法，多視圖聚類算法可以更有效地完成聚類任務；②相比較魯棒的多視圖均值聚類和極小化極大值優化兩種多視圖聚類算法，多視圖模糊緊致性分離性算法不但在未添加噪聲數據時具有較高準確率，而且在添加噪聲數據后展現出較高魯棒性。

3.3 參數討論

算法中存在m、γ和β這3個參數。為了評估參數對算法的影響，在實驗數據集上進行了實驗。實驗結果如圖1～圖4所示，縱坐標Acc表示聚類準確率。

圖1 IS數據集上參數對聚類結果的影響

圖2 MF數據集上參數對聚類結果的影響

圖3 MMKSD數據集上參數對聚類結果的影響

圖4 Cal數據集上參數對聚類結果的影響

從圖1～圖4可以得出參數m、γ和β對聚類結果的影響：①參數β最為穩定，對準確率的影響也最小；②參數γ穩定性在數據集IS、MMKSD和Cal數據集上表現較好，在MF數據集上比較敏感；③聚類結果對參數m的取值最為敏感，這與極小化極大值優化算法對參數m的分析一致。

從圖1～圖4可以得出以下結論：①參數m、γ和β對聚類結果存在一定影響，尤其是參數m的取值對聚類準確率影響較大；②相對于聚類準確率，參數m、γ和β對算法魯棒性的影響較小，即無論參數m、γ和β如何取值，當數據集中加入一定比例的噪聲時，準確率的變化均較小。

4 結束語

在數據規模日趨龐大的同時，更多的噪聲摻雜其中，數據的結構和形式也愈加復雜多樣。更全面、穩定地發現數據背后潛藏的知識，是研究多視圖聚類算法以及聚類魯棒性的初衷。

文中提出了一種多視圖模糊緊致性分離性算法。該算法一方面保持了多視圖聚類算法的特點，聚類時根據不同視圖的重要性協同聚類，有助于提高聚類準確率；另一方面繼承了模糊緊致性分離性算法綜合考慮類內緊致性和類間分離性的優點，能夠增強算法的魯棒性。在聚類過程中，該算法通過權重來調整每個視圖之間聚類結果的一致性，且能夠自動學習并更新權重。為了對算法進行評估，選取了4個多視圖數據集進行了實驗，并分為未添加噪聲數據和添加噪聲數據兩種情況。實驗結果表明，文中算法在聚類準確率和魯棒性方面的表現均優于對比算法。