吳建國,魏 巍,2,郭鑫垚,閆 京

1(山西大學(xué) 計算機(jī)與信息技術(shù)學(xué)院,太原 030006)

2(山西大學(xué) 計算智能與中文信息處理教育部重點(diǎn)實驗室,太原 030006)

1 引 言

聚類分析是機(jī)器學(xué)習(xí)中一種典型的無監(jiān)督算法[1],聚類算法依據(jù)相似性原理將一組數(shù)據(jù)對象劃分為一定數(shù)量的同質(zhì)組(簇),使得同簇內(nèi)數(shù)據(jù)對象有較高的相似度,不同簇內(nèi)數(shù)據(jù)對象相似度較低.聚類分析也是文本挖掘[2,3]、社區(qū)發(fā)現(xiàn)[4-6]、推薦系統(tǒng)[7,8]以及圖像處理[9,10]的核心技術(shù).聚類概念被提出幾十年以來,涌現(xiàn)出了大量的聚類算法[11].然而,這些聚類算法普遍存在一些不足,如不同的聚類算法具有不同的目標(biāo)函數(shù),導(dǎo)致其只能處理特定的數(shù)據(jù)結(jié)構(gòu)和特定形狀的聚類;一些聚類算法高度依賴于初始化參數(shù),如K-means算法等.為解決以上單一聚類算法的各種不足,同時為應(yīng)對單一的聚類算法無法有效處理當(dāng)前多樣化數(shù)據(jù)類型和復(fù)雜數(shù)據(jù)分布的挑戰(zhàn),研究人員將集成學(xué)習(xí)技術(shù)應(yīng)用于聚類分析算法,提出了聚類集成的概念.

聚類集成又可稱為聚類融合,其算法的思想為使用不同的聚類算法,或同一聚類算法設(shè)置不同初始化參數(shù)得到基聚類集合.在此基礎(chǔ)上,對基聚類結(jié)果使用組合策略進(jìn)行集成,獲得最終聚類集成結(jié)果,以此提升聚類算法的聚類準(zhǔn)確性和魯棒性[12].然而,傳統(tǒng)聚類集成方法無法自動的評估基聚類的質(zhì)量,等權(quán)重的考慮每個基聚類,容易受到低質(zhì)量基聚類的影響.為減輕低質(zhì)量基聚類對聚類集成結(jié)果的影響,通常根據(jù)基聚類的質(zhì)量好壞賦予其不同的權(quán)重,質(zhì)量較好的基聚類賦予較高權(quán)重,反之較低.Berikov等人[13]在理論上證明了加權(quán)聚類集成算法的必要性.在一定的假設(shè)情況下,任意一對樣本被錯分的概率隨著聚類集成規(guī)模的加大而趨于收斂,因此在時間以及存儲有限的情況下,聚類集成規(guī)模較小時,對基聚類進(jìn)行加權(quán)是非常有必要的.Li等人[14]將聚類集成問題轉(zhuǎn)化為非負(fù)矩陣分解的問題,提出了一種非負(fù)矩陣加權(quán)的聚類集成算法,在非負(fù)矩陣分解的過程中為每個基聚類賦予不同的權(quán)重.Xue等人[15]提出了一種基于地標(biāo)點(diǎn)的譜聚類算法,首先使用該算法生成基聚類集合,然后以信息熵為依據(jù)計算各基聚類的不確定性,并根據(jù)不確定性的大小確定基聚類的權(quán)重.Huang等人[16]提出了一種基于局部加權(quán)的聚類集成算法,采用熵準(zhǔn)則評估基聚類中各個簇的不確定性,依據(jù)該不確定性進(jìn)行共協(xié)關(guān)系矩陣的局部加權(quán),并基于此共協(xié)關(guān)系矩陣分別采用層次聚類算法及圖分割算法得到聚類集成結(jié)果.Xu等人[17]將簇的可靠性評估轉(zhuǎn)化為粗糙集中的不確定性度量問題,同時設(shè)計了一種樣本局部相似性度量方法,將這兩種度量方法用于對共協(xié)關(guān)系矩陣的加權(quán),并基于此共協(xié)關(guān)系矩陣求得聚類集成結(jié)果.

雖然上述加權(quán)聚類集成方法能夠很好的從不同層次評估其質(zhì)量并賦予其不同的權(quán)重,但該類方法往往基于歐氏距離,而歐式距離對數(shù)據(jù)的所有特征等權(quán)重考慮.相比之下,馬氏距離考慮數(shù)據(jù)特征之間相關(guān)性以及差異性,可以更好的刻畫樣本之間的相似性.因此,本文受馬氏距離度量學(xué)習(xí)的啟發(fā),提出了一種度量學(xué)習(xí)引導(dǎo)的加權(quán)聚類集成算法(WEC-ML),該方法在學(xué)習(xí)樣本間的馬氏距離度量的同時,考慮每個基聚類結(jié)果中樣本對的劃分,將大多數(shù)基聚類結(jié)果認(rèn)為相似的樣本對拉近,將基聚類結(jié)果認(rèn)為不相似的樣本對推遠(yuǎn).通過以上過程,求得新的馬氏距離度量,在新的投影空間中賦予各個基聚類新的權(quán)重.進(jìn)一步,本文將馬氏距離度量學(xué)習(xí)與基聚類權(quán)重學(xué)習(xí)相融合,相互指導(dǎo),在不斷迭代中求得最優(yōu)權(quán)重,從而提升聚類集成算法性能.

本文主要貢獻(xiàn)總結(jié)如下:

1)提出了一種度量學(xué)習(xí)引導(dǎo)的加權(quán)聚類集成算法.算法在每次迭代中學(xué)習(xí)不同基聚類的權(quán)重并進(jìn)行聚類集成,基于集成結(jié)果構(gòu)建成對約束,學(xué)習(xí)新的馬氏距離度量,將劃分為同簇的樣本拉近,不同簇的樣本推遠(yuǎn),并在新的投影空間中為基聚類結(jié)果學(xué)習(xí)新的權(quán)重.

2)將馬氏距離度量學(xué)習(xí)與基聚類權(quán)重學(xué)習(xí)整合到同一個優(yōu)化問題中,實現(xiàn)了二者的相互指導(dǎo).

3)在12個真實數(shù)據(jù)集上的實驗結(jié)果表明,聚類集成效果有明顯提升,表明馬氏距離度量學(xué)習(xí)對于基聚類加權(quán)的有效性.

2 相關(guān)工作

2.1 度量學(xué)習(xí)

度量學(xué)習(xí)利用樣本標(biāo)簽信息生成約束,將同類樣本之間的距離拉近,不同類樣本之間的距離推遠(yuǎn),學(xué)到一個更加準(zhǔn)確刻畫樣本之間的相似性度量[18].廣泛來說,可認(rèn)為度量學(xué)習(xí)學(xué)習(xí)到了一個特征表示空間,在該空間中樣本之間的距離度量能反映出數(shù)據(jù)的特性.距離度量對許多機(jī)器學(xué)習(xí)方法性能具有重要的作用,如經(jīng)典聚類方法K-means涉及到樣本之間距離的計算,學(xué)習(xí)合適的距離度量可以有效的提升聚類性能.傳統(tǒng)歐式距離假設(shè)數(shù)據(jù)不同的特征重要性相同,并且數(shù)據(jù)特征相互獨(dú)立.然而這種假設(shè)在真實場景中一般是不成立的,因此往往需要使用更加通用的馬氏距離[19]度量樣本對之間的相似性.馬氏距離度量的定義如下:

(1)

其中,M反映了樣本特征之間的關(guān)聯(lián)性以及樣本特征的權(quán)重.M為半正定矩陣,當(dāng)M為單位矩陣時,馬氏距離會退化為歐式距離.

2.2 聚類集成

聚類集成是指給定一個基聚類集合,通過對該基聚類集合進(jìn)行融合以獲取數(shù)據(jù)的團(tuán)簇結(jié)構(gòu),從而得到相比于現(xiàn)有聚類結(jié)果更加魯棒、更加穩(wěn)健的聚類集成結(jié)果[20].與傳統(tǒng)聚類方法相比,聚類集成算法更具有普遍性、準(zhǔn)確性和魯棒性.因此,聚類集成算法得到廣泛的研究與應(yīng)用.聚類集成過程通常分為兩個步驟,分別為基聚類生成和一致性函數(shù)的設(shè)計[21].常用的基聚類生成方法有:同一聚類算法使用不同的初始化參數(shù)(不同的初始狀態(tài)),如K-means算法設(shè)置不同的初始簇中心點(diǎn);同一數(shù)據(jù)集,使用不同的聚類算法[22];同一算法在不同數(shù)據(jù)集的子集進(jìn)行聚類[23];通過聚類評價指標(biāo)挑選基聚類[24].采用不同的基聚類生成方法生成基聚類集合后,需將其轉(zhuǎn)化為統(tǒng)一的、綜合的聚類結(jié)果,即一致性函數(shù)的設(shè)計.根據(jù)一致性函數(shù)設(shè)計方法的不同,現(xiàn)有聚類集成算法可分為:基于共協(xié)關(guān)系矩陣的聚類集成算法、基于圖劃分的聚類集成算法等.

基于共協(xié)關(guān)系矩陣的聚類集成算法通過統(tǒng)計兩個樣本在多個基聚類結(jié)果中出現(xiàn)在同一簇的次數(shù)構(gòu)建共協(xié)關(guān)系矩陣,并利用該矩陣中元素的取值衡量兩個樣本之間的相似性.Fred等人[20]首次提出了共協(xié)關(guān)系矩陣的概念,并提出了證據(jù)累積聚類集成算法(EAC),該方法可識別任意形狀、大小的簇,但是算法時間復(fù)雜度較高.Wang等人[25]對EAC算法進(jìn)行了擴(kuò)展,提出了概率累積的方法,該方法考慮了原始聚類中簇的大小,相比于EAC算法效率明顯提升.Zhong等人[26]利用樣本對之間距離的累積表示它們出現(xiàn)在同一個簇的概率,并以此代替它們出現(xiàn)在同簇中的頻率,實現(xiàn)對共協(xié)關(guān)系矩陣的構(gòu)建和加權(quán).Huang等人[16]提出了一種基于熵準(zhǔn)則的簇不確定性評估方法,并利用該不確定性實現(xiàn)對共協(xié)關(guān)系矩陣的局部加權(quán).Yi等人[27]構(gòu)造共協(xié)關(guān)系矩陣時過濾掉矩陣中的不確定項,隨后使用矩陣補(bǔ)全技術(shù)完成對不確定項的補(bǔ)全.Li等人[28]以共協(xié)關(guān)系矩陣為基礎(chǔ),提出一種新的層次聚類方法,通過引入歸一化邊緣的概念度量簇之間的相似性.Liu等人[29]提出了一種基于共協(xié)關(guān)系矩陣的譜聚類(SEC)集成算法,在理論上證明了譜聚類與加權(quán)K-means算法的等價性.Tao等人[30]提出了一種魯棒的譜聚類集成算法,該算法通過低秩約束學(xué)習(xí)共協(xié)關(guān)系矩陣的魯棒表示,去除共協(xié)關(guān)系矩陣中的各種噪聲.

基于圖劃分的聚類集成算法,該類算法的基本思想為將各基聚類結(jié)果轉(zhuǎn)換為圖,然后在此圖上采用不同的圖劃分算法,以此得到聚類集成結(jié)果.Strehl等人[31]提出了3種代表性的基于圖劃分的聚類集成算法,分別為基于簇相似分割算法CSPA(Cluster-based Similarity Partitioning Algorithm),超圖分割算法HGPA(Hyper Graph Partitioning Algorithm)以及元聚類算法MCLA(Meta-Clustering Algorithm).CSPA算法將樣本點(diǎn)作為圖中節(jié)點(diǎn),以樣本點(diǎn)之間的歐式距離來表示邊,然后使用METIS[32]算法對圖進(jìn)行劃分,以此得到聚類集成結(jié)果.HGPA算法同樣將樣本點(diǎn)作為圖中節(jié)點(diǎn),由樣本中的每一個簇表示邊,同樣使用METIS[32]算法進(jìn)行圖的劃分.MCLA算法將基聚類的所有簇作為圖中節(jié)點(diǎn),邊由簇之間共有樣本點(diǎn)占整個數(shù)據(jù)集的比重來表示,然后使用METIS[32]算法將圖劃分為多個類,最后依據(jù)樣本點(diǎn)在每個劃分類中出現(xiàn)的比例得到聚類集成結(jié)果.由于CSPA、HGPA兩種算法在構(gòu)建圖時分別只考慮了樣本之間、基聚類之間的相似性,可能帶來信息缺失.因此Fern等人[33]提出了HBGF(Hybrid Bipartite Graph Formulation)算法,該算法將樣本點(diǎn)以及簇作為圖中節(jié)點(diǎn)來構(gòu)建二部圖,隨后使用METIS[32]算法將圖進(jìn)行劃分得到聚類集成結(jié)果.Huang等人[34]提出一種基于稀疏圖表示以及隨機(jī)游走的圖聚類集成算法,樣本代表圖中節(jié)點(diǎn),邊由樣本之間相似度表示,利用隨機(jī)游走方法對每條邊加權(quán),最后進(jìn)行圖劃分得到聚類集成結(jié)果.Mimaroglu等人[35]構(gòu)建了樣本之間的相似圖,并通過尋找支點(diǎn)和擴(kuò)展簇對圖進(jìn)行劃分得到聚類集成結(jié)果.Yu等人[36]設(shè)計了一種基于雙親和傳播的聚類集成框架,能夠有效處理數(shù)據(jù)中的噪聲,并通過歸一化切割算法得到最終的聚類集成結(jié)果.

現(xiàn)有聚類集成算法大多只考慮如何將多個基聚類進(jìn)行集成,往往忽略了基聚類本身質(zhì)量所帶來的影響.然而,在聚類集成中,基聚類質(zhì)量往往嚴(yán)重影響聚類集成算法的性能.Fred等人[20]首次提出共協(xié)關(guān)系矩陣的證據(jù)累積聚類集成算法(EAC),該方法平等對待各基聚類,整體性能容易受到質(zhì)量較差基聚類的影響.為了降低低質(zhì)量基聚類對集成結(jié)果的影響,研究人員提出了基聚類加權(quán)的聚類集成算法[14-17],為質(zhì)量較好的基聚類賦予較高權(quán)重,同時降低較差基聚類的權(quán)重.然而當(dāng)前聚類集成算法研究中,如何高效地評估各個基聚類的質(zhì)量,是一個較為困難的問題.為解決以上問題,本文提出一種度量學(xué)習(xí)引導(dǎo)的加權(quán)聚類集成算法,本算法在學(xué)習(xí)馬氏距離度量的同時,考慮不同基聚類結(jié)果中樣本對的劃分,將大多數(shù)基聚類結(jié)果認(rèn)為相似的樣本對拉近,將基聚類結(jié)果認(rèn)為不相似的樣本對推遠(yuǎn),在新的馬氏距離的投影空間下,評估各基聚類的重要性,并賦予其新的權(quán)重.與傳統(tǒng)方法不同之處在于,提出的方法將馬氏距離度量學(xué)習(xí)與基聚類賦權(quán)的過程融合,從而有效提升了聚類集成算法的性能.

3 度量學(xué)習(xí)引導(dǎo)的加權(quán)聚類集成算法

本節(jié)介紹所提算法WEC-ML中所使用的相關(guān)符號,構(gòu)建了聚類集成算法模型,給出了模型的求解過程簡述了算法的步驟以及算法的時間復(fù)雜度分析.

3.1 模型相關(guān)符號定義

給定數(shù)據(jù)集X={x1,x2,…,xn}∈n×d,其中n表示樣本個數(shù),d表示樣本維度,xi表示數(shù)據(jù)集中第i個樣本點(diǎn).對數(shù)據(jù)集進(jìn)行T次聚類,得到T個基聚類結(jié)果:

P={P1,P2,…,PT}

在T個基聚類中,第t個基聚類的連接矩陣可定義為:

(2)

表示在第t個基聚類中若樣本對i和j屬于同一個簇,則其對應(yīng)的矩陣元素值為1,反之則為-1.

Fred和Jain[20]首次提出共協(xié)關(guān)系矩陣的定義,共協(xié)關(guān)系矩陣表示樣本對在所有基聚類中出現(xiàn)在同一個簇的頻率.基于此,集成T個基聚類的共協(xié)關(guān)系矩陣S可表示為:

(3)

其中,sij∈[-1,1]表示樣本i和樣本j在T個基聚類結(jié)果中出現(xiàn)在同一個簇的頻率.sij越大,表示樣本i與樣本j越相似,反之,越不相似.

3.2 模型定義

現(xiàn)有聚類集成算法大多無法自動評估各基聚類的質(zhì)量,平等的對待各基聚類,忽略了基聚類質(zhì)量對于集成結(jié)果的影響.在聚類集成過程中,若生成的基聚類質(zhì)量較差,對集成結(jié)果也會有一定影響.為獲得或挑選更高質(zhì)量的基聚類集合,可在基聚類生成階段挑選高質(zhì)量的基聚類作為基聚類集合,在集成階段,通過設(shè)計不同一致性函數(shù),對每個基聚類進(jìn)行評估,賦予不同的權(quán)重.

下面給出一種加權(quán)共協(xié)關(guān)系矩陣的定義:

(4)

現(xiàn)有聚類集成算法大多基于歐氏距離空間,通過集成多個基聚類得到聚類集成結(jié)果,以提升聚類性能.然而歐式距離空間對數(shù)據(jù)的所有特征等權(quán)重考慮,相比之下,馬氏距離考慮特征之間相關(guān)性和差異性,可以更好的刻畫樣本之間的相似性.因此本文受馬氏距離度量學(xué)習(xí)的啟發(fā),提出了一種度量學(xué)習(xí)引導(dǎo)的加權(quán)聚類集成算法,該方法在學(xué)習(xí)樣本間的馬氏距離度量的同時考慮不同基聚類結(jié)果中樣本對的劃分情況.對應(yīng)優(yōu)化問題可表示為:

(5)

本方法將多個基聚類加權(quán)過程與馬氏距離度量學(xué)習(xí)統(tǒng)一到一個框架中,兩個過程相互指導(dǎo).此外,模型中還引入了兩個正則化項用于指導(dǎo)約束基聚類的加權(quán)過程.

因此,目標(biāo)函數(shù)改寫為:

(6)

模型中第2項為馬氏距離矩陣的正則化項,用于保證矩陣的稀疏性.第3項為各個基聚類權(quán)重向量的正則化項,用于約束各個基聚類賦予的權(quán)重差異,若權(quán)重值過大會賦予較大的懲罰.

3.3 模型求解

提出的模型有兩個需要求解的變量,即馬氏距離矩陣M以及權(quán)重向量α.本文采用迭代交替優(yōu)化的方法進(jìn)行模型求解,求解過程如下:

1)固定權(quán)重向量α,求解馬氏距離矩陣M

當(dāng)權(quán)重向量α固定,去掉無關(guān)項,式(6)的優(yōu)化問題可表示為:

(7)

對M求偏導(dǎo),并令偏導(dǎo)等式等于零,則有:

(8)

因為權(quán)重向量α固定,所以sij值為常量.因此,由式(8)可得:

(9)

2)固定馬氏距離矩陣M,求解權(quán)重向量α

當(dāng)馬氏距離矩陣M固定,式(6)的優(yōu)化問題可表示為:

(10)

則有:

(11)

因此,式(6)的優(yōu)化問題等價于:

(12)

上述優(yōu)化問題是一個標(biāo)準(zhǔn)的二次規(guī)劃問題,可以使用常規(guī)優(yōu)化方法[37]求得最優(yōu)解.

3.4 算法步驟

基于模型求解過程,可以給出度量學(xué)習(xí)引導(dǎo)的加權(quán)聚類集成算法的描述:

輸入:數(shù)據(jù)集X,聚類簇數(shù)k,超參數(shù)λ及β.

輸出:聚類集成結(jié)果π.

步驟1.對數(shù)據(jù)集X運(yùn)用聚類算法生成T個基聚類,P={P1,P2,…,PT};

步驟2.依據(jù)式(2)得到每個基聚類結(jié)果對應(yīng)的連接矩陣Gt;

步驟3.初始化各個基聚類權(quán)重值,賦予各個基聚類相同的權(quán)重;

步驟4.依據(jù)式(4)獲得更新加權(quán)的共協(xié)關(guān)系矩陣S;

步驟5.依據(jù)式(9)求解更新馬氏距離矩陣M;

步驟6.依據(jù)式(12)求解更新各基聚類的權(quán)重值αt;

步驟7.重復(fù)步驟4～步驟6,直到各基聚類的權(quán)重值趨于收斂或者達(dá)到最大迭代次數(shù);

步驟8.在加權(quán)的共協(xié)關(guān)系矩陣S上執(zhí)行層次聚類算法,得到最終聚類集成結(jié)果.

3.5 時間復(fù)雜度分析

本節(jié)根據(jù)3.4節(jié)算法步驟,對所提算法WEC-ML的時間復(fù)雜度進(jìn)行分析,主要根據(jù)聚類集成算法基聚類生成階段(步驟1～步驟3)和一致性函數(shù)學(xué)習(xí)階段計算(步驟4～步驟8).

基聚類生成階段,生成T個基聚類的時間復(fù)雜度為Ο(Ttc),其中tc表示生成一個基聚類的時間復(fù)雜度.基聚類結(jié)果轉(zhuǎn)換為連接矩陣的時間復(fù)雜度為Ο(Ttg),其中tg表示一個基聚類轉(zhuǎn)換為對應(yīng)連接矩陣的時間復(fù)雜度.因此,基聚類生成階段時間復(fù)雜度可表示為Ο(T(tc+tg)).

一致性函數(shù)學(xué)習(xí)階段,循環(huán)體主要包括3個步驟,即加權(quán)的共協(xié)關(guān)系矩陣S的生成、馬氏距離矩陣M的計算更新以及各個基聚類權(quán)重αt的更新.

1)加權(quán)的共協(xié)關(guān)系矩陣S的生成為T個連接矩陣與權(quán)重向量的相乘相加.因此,更新S的時間復(fù)雜度可表示為Ο(T).

2)馬氏距離矩陣M的求解為n對向量相乘相加.因此,更新M的時間復(fù)雜度可表示為Ο(n2).

3)由于各基聚類權(quán)重αt的更新是標(biāo)準(zhǔn)凸的二次規(guī)劃問題,可以使用橢球法在多項式時間內(nèi)求解.因此,更新各基聚類權(quán)重的時間復(fù)雜度可表示為Ο(P(m)),其中P(·)表示一個多項式函數(shù).

假設(shè)一致性函數(shù)學(xué)習(xí)階段迭代次數(shù)為Niter,因此一致性函數(shù)學(xué)習(xí)階段的時間復(fù)雜度可表示為Ο(Niter(T+n2+P(m))).

綜上所述,所提出算法WEC-ML總時間復(fù)雜度為Ο(T(tc+tg))+Ο(Niter(T+n2+P(m))).

4 實驗結(jié)果及分析

為驗證度量學(xué)習(xí)引導(dǎo)的加權(quán)聚類集成算法(WEC-ML)的有效性及性能,采用UCI數(shù)據(jù)集對提出算法進(jìn)行驗證.實驗運(yùn)行環(huán)境如下:PC配置為Inter(R)Xeon(R)Gold 6254 CPU@3.10GHz,512GB,系統(tǒng)為Windows10,代碼執(zhí)行軟件為MATLAB 2022b.

4.1 數(shù)據(jù)集與評價指標(biāo)

本文選取了Breast、Control、Dermatology、Ecoli、Glass、Ionosphere、Iris、Wine、Yeast Appendicitis、Newthyroid、Wdbc 12個UCI數(shù)據(jù)集進(jìn)行實驗分析,數(shù)據(jù)集的詳細(xì)描述如表1所示,實驗中為了避免數(shù)據(jù)集中特征之間差異對集成結(jié)果造成影響,對所有數(shù)據(jù)集進(jìn)行了歸一化處理.

表1 數(shù)據(jù)集詳細(xì)信息

為評估聚類集成結(jié)果的準(zhǔn)確性,采用調(diào)整蘭德系數(shù)(Adjusted Rand Index,ARI)[38]、標(biāo)準(zhǔn)互信息(Normalized Mutual Information,NMI)[31]兩種常用的聚類評價指標(biāo)對其進(jìn)行評價.ARI與NMI結(jié)果取值范圍均為[0,1],結(jié)果越接近1,集成結(jié)果與真實結(jié)果越接近,說明算法的集成效果越好.

調(diào)整蘭德系數(shù)(ARI)通過計算兩個聚類結(jié)果中的樣本對是否屬于相同簇來獲得.從廣義角度講,ARI用于衡量兩個數(shù)據(jù)分布的相似程度.其計算公式如下:

(13)

其中,N11表示樣本對既在基聚類π′中屬于同簇,同時在基聚類πG中屬于同簇的個數(shù);N00表示樣本對在基聚類π′中不屬于同簇,同時在基聚類πG中也不屬于同簇的個數(shù);N10表示樣本對在基聚類π′中屬于同一個簇,但在基聚類πG中不屬于同一個簇的個數(shù);N01表示樣本對在基聚類π′中不屬于同一個簇而在基聚類πG中屬于同簇的個數(shù).

標(biāo)準(zhǔn)互信息(NMI)從信息論角度評估真實聚類結(jié)果與現(xiàn)有聚類結(jié)果的相似度,其計算公式如下:

(14)

其中,Nij表示聚類結(jié)果第i個簇中包含原數(shù)據(jù)集類標(biāo)簽為j的樣本總數(shù),Ni表示聚類結(jié)果中第i個簇的樣本總數(shù),Nj表示原數(shù)據(jù)集類標(biāo)簽為j的樣本總數(shù),N表示樣本總數(shù).ks和kt分別表示聚類得到的簇個數(shù)和原數(shù)據(jù)集的類個數(shù).

4.2 實驗設(shè)置

實驗中,每個基聚類的初始化權(quán)重設(shè)置為αt=1/T,t=1,2,…,T.權(quán)衡參數(shù)λ及β參數(shù)范圍均為{10-4,10-3,10-2,10-1,100,101,102,103,104}.本文使用K-means算法生成T個基聚類,其中集成規(guī)模T設(shè)置為20.為了保證各個基聚類之間的差異性,本算法聚類簇數(shù)k值的選擇范圍為[K,50],其中K為數(shù)據(jù)集真實簇數(shù).為保證實驗的公平性,對比算法涉及到的實驗參數(shù)均與其原文保持一致.為了減少到實驗的隨機(jī)性的影響,每個算法均運(yùn)行20次,計算平均ARI、NMI值及對應(yīng)的標(biāo)準(zhǔn)差.

4.3 對比實驗

為了驗證所提WEC-ML算法性能,將其與EAC[20],LWEA[16],MCLA[31],MDEC-HC[23],NMFC[39],PTGP[36],RSEC[30]聚類集成算法進(jìn)行比較.實驗結(jié)果如表2及表3所示,表中每個數(shù)據(jù)集的最優(yōu)結(jié)果已加粗展示,括號內(nèi)為標(biāo)準(zhǔn)差.

表2 不同算法在數(shù)據(jù)集上的平均NMI值(T=20)

表3 不同算法在數(shù)據(jù)集上的平均ARI值(T=20)

通過分析表2和表3的實驗數(shù)據(jù)可得,相比于對比算法,本文提出的WEC-ML算法在所有數(shù)據(jù)集上的NMI值均有顯著的提升.雖然在Control、Dermatology、Glass以及Wdbc數(shù)據(jù)集上WEC-ML算法的ARI值不是最優(yōu)但仍是次優(yōu)結(jié)果.此外,相比于各基聚類等權(quán)重考慮的證據(jù)累積(EAC)、非負(fù)矩陣分解(NMFC)算法,WEC-ML算法的NMI、ARI均有明顯提升,表明了WEC-ML算法對各基聚類賦予不同權(quán)重后再進(jìn)行聚類集成的有效性.與此同時,相比于基于熵準(zhǔn)則加權(quán)的聚類集成算法(LWEA),WEC-ML算法也有一定的優(yōu)勢,也表明了所提算法在基聚類加權(quán)方面的優(yōu)勢.

4.4 參數(shù)敏感性分析

通過對所提算法WEC-ML在每個數(shù)據(jù)集上采用不同參數(shù)得到的NMI值進(jìn)行可視化展示,進(jìn)行了參數(shù)敏感性分析.在提出的算法中,超參數(shù)λ及β會影響模型性能,其中λ用于控制馬氏距離矩陣M的稀疏程度,β用于控制各個基聚類權(quán)重均衡程度.通過調(diào)整λ及β的值,并記錄每個數(shù)據(jù)集的NMI值,實驗結(jié)果如圖1所示.當(dāng)λ及β取不同值時NMI值有一定程度的波動.由圖1可以看出,WEC-ML在Appendicitis、Breast、Ecoli、Iris、Wdbc、Wine數(shù)據(jù)集上對參數(shù)變化較為敏感,并且往往是在λ固定,β不同的情況下,WEC-ML的NMI值比較敏感.而在Control、Dermatology、Glass、Ionosphere、Newthyroid、Yeast數(shù)據(jù)集上對參數(shù)變化不太敏感.

圖1 算法在不同參數(shù)下的平均NMI值

4.5 集成規(guī)模分析以及迭代情況

為進(jìn)一步評估所提方法的穩(wěn)健性,比較了不同集成規(guī)模下不同聚類集成算法的性能.在不同的數(shù)據(jù)集上運(yùn)行不同聚類集成算法,其中,集成規(guī)模范圍為{10,20,30,40,50},實驗結(jié)果如圖2所示.可以看出,雖然NMFC、MDEC-HC算法在Glass、Wdbc和Wine上部分集成規(guī)模優(yōu)于所提算法,但是在其他數(shù)據(jù)集上,所提算法與對比算法相比產(chǎn)生了最好或者接近最好的結(jié)果.特別是,在Appendicitis、Breast、Ionosphere 以及Iris數(shù)據(jù)集上,所提算法在不同集成規(guī)模下均優(yōu)于對比算法.并且,隨著集成規(guī)模的變化,對比實驗的NMI值波動明顯,而WEC-ML算法的運(yùn)行效果較為平穩(wěn).

圖2 不同算法在不同集成規(guī)模下的平均NMI值

通過對各數(shù)據(jù)集上算法迭代收斂次數(shù)的分析,可以得到大部分算法的迭代次數(shù)小于5,只有Appendicitis、Wine、Yeast迭代次數(shù)分別為9、5、7.表明WEC-ML算法可以在有限時間內(nèi)求得各基聚類的最優(yōu)權(quán)重.

5 結(jié) 論

本文提出了一種度量學(xué)習(xí)引導(dǎo)的加權(quán)聚類集成算法.該算法根據(jù)聚類集成結(jié)果構(gòu)建的成對約束學(xué)習(xí)馬氏距離度量,并將馬氏距離度量學(xué)習(xí)與基聚類權(quán)重學(xué)習(xí)整合到同一個優(yōu)化問題中,實現(xiàn)了二者的相互指導(dǎo),在充分地挖掘成對約束關(guān)系的基礎(chǔ)上,同時降低了低質(zhì)量基聚類對聚類集成結(jié)果的不良影響.實驗分析表明度量學(xué)習(xí)引導(dǎo)的加權(quán)聚類集成算法的性能優(yōu)于現(xiàn)有的代表性聚類集成算法.然而,在許多實際問題中簡單的應(yīng)用馬氏距離度量難以刻畫樣本之間的關(guān)系,因此如何將本文思想擴(kuò)展到深度聚類集成算法是一個值得研究的問題.