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

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

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

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

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

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

1 模糊緊致性分離性算法

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

(1)

(2)

(3)

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

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

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

2.1 算法的目標(biāo)函數(shù)

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

(4)

其中，

(5)

(6)

(7)

(8)

算法通過優(yōu)化如式(4)所示的目標(biāo)函數(shù)，產(chǎn)生多視圖的聚類結(jié)果。在聚類過程中，首先利用視圖權(quán)重α(p)整合不同視圖的信息，然后用隸屬度矩陣U返回不同視圖一致的聚類結(jié)果。

2.2 算法的優(yōu)化

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

(9)

2.2.1 固定質(zhì)心和權(quán)重并求解隸屬度

將質(zhì)心和權(quán)重視為常量，隸屬度視為變量，對式(9)關(guān)于uci求偏導(dǎo)，并令偏導(dǎo)數(shù)等于0，可得

(10)

(11)

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

(12)

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

2.2.2 固定權(quán)重和隸屬度并求解質(zhì)心

將權(quán)重和隸屬度視為常量，質(zhì)心視為變量，對式(9)關(guān)于vc(p)求偏導(dǎo)，并令偏導(dǎo)數(shù)等于0，可得

(13)

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

(14)

2.2.3 固定質(zhì)心和權(quán)重并求解隸屬度

將隸屬度和質(zhì)心視為常量，權(quán)重向量α(p)視為變量，對式(9)關(guān)于α(p)求偏導(dǎo)，并令偏導(dǎo)數(shù)等于0，可得

(15)

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

(16)

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

2.3 算法的步驟

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

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

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

輸出 聚類結(jié)果向量q。

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

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

③ 初始化當(dāng)前迭代次數(shù)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

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

3 實驗分析

實驗的環(huán)境為操作系統(tǒng)Windows 7，CPU型號Inter i3-4150，頻率3.50GHz，內(nèi)存4GB，編譯軟件為MATLAB R2016a。

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

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

3.1 實驗準(zhǔn)備

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

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

表1 多視圖數(shù)據(jù)集的詳細信息

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

3.2 實驗結(jié)果

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

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

表2 在有無噪聲兩種情況下IS數(shù)據(jù)集上的準(zhǔn)確率對比

表3 在有無噪聲兩種情況下MF數(shù)據(jù)集上的準(zhǔn)確率對比

表4 在有無噪聲兩種情況下MMKSD數(shù)據(jù)集上的準(zhǔn)確率對比

表5 在有無噪聲兩種情況下Cal數(shù)據(jù)集上的準(zhǔn)確率對比

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

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

3.3 參數(shù)討論

算法中存在m、γ和β這3個參數(shù)。為了評估參數(shù)對算法的影響，在實驗數(shù)據(jù)集上進行了實驗。實驗結(jié)果如圖1～圖4所示，縱坐標(biāo)Acc表示聚類準(zhǔn)確率。

圖1 IS數(shù)據(jù)集上參數(shù)對聚類結(jié)果的影響

圖2 MF數(shù)據(jù)集上參數(shù)對聚類結(jié)果的影響

圖3 MMKSD數(shù)據(jù)集上參數(shù)對聚類結(jié)果的影響

圖4 Cal數(shù)據(jù)集上參數(shù)對聚類結(jié)果的影響

從圖1～圖4可以得出參數(shù)m、γ和β對聚類結(jié)果的影響：①參數(shù)β最為穩(wěn)定，對準(zhǔn)確率的影響也最??；②參數(shù)γ穩(wěn)定性在數(shù)據(jù)集IS、MMKSD和Cal數(shù)據(jù)集上表現(xiàn)較好，在MF數(shù)據(jù)集上比較敏感；③聚類結(jié)果對參數(shù)m的取值最為敏感，這與極小化極大值優(yōu)化算法對參數(shù)m的分析一致。

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

4 結(jié)束語

在數(shù)據(jù)規(guī)模日趨龐大的同時，更多的噪聲摻雜其中，數(shù)據(jù)的結(jié)構(gòu)和形式也愈加復(fù)雜多樣。更全面、穩(wěn)定地發(fā)現(xiàn)數(shù)據(jù)背后潛藏的知識，是研究多視圖聚類算法以及聚類魯棒性的初衷。

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