莊景暉

（漳州職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)工程系，福建 漳州 363000）

0 引 言

聚類分析作為一種重要的數(shù)據(jù)挖掘處理技術(shù)，近幾年來在生物信息學(xué)［1］、文本挖掘［2］和社區(qū)發(fā)現(xiàn)［3］等許多領(lǐng)域已經(jīng)得到了廣泛的應(yīng)用。作為一種無監(jiān)督的分類方法，聚類分析主要目的是根據(jù)某些預(yù)先定義的標(biāo)準(zhǔn)對(duì)數(shù)據(jù)集進(jìn)行劃分，進(jìn)而形成多個(gè)簇類，劃分的結(jié)果使得簇內(nèi)的樣本盡可能相似，不同簇間的樣本盡可能相異［4］?，F(xiàn)今，隨著信息技術(shù)的飛速發(fā)展，數(shù)據(jù)的采集變得更加方便與迅速，也因此導(dǎo)致了人們獲得的數(shù)據(jù)集變得更大、更復(fù)雜。與低維數(shù)據(jù)相比，在高維數(shù)據(jù)空間中通常存在著許多并不相關(guān)的屬性［5］，同時(shí)還存在著“維度效應(yīng)”的問題，從而導(dǎo)致多數(shù)傳統(tǒng)聚類分析方法無法有效地聚類分析高維數(shù)據(jù)。為了解決這類問題，國內(nèi)外研究人員針對(duì)高維數(shù)據(jù)的分析提出了很多的聚類方法［6］，其中的子空間聚類就是一類代表性的方法。

子空間聚類是指在高維數(shù)據(jù)空間中挖掘存在于某些低維子空間中簇類的技術(shù)［7］。它將數(shù)據(jù)集劃分并形成多個(gè)簇類，從中尋找出數(shù)據(jù)集中各個(gè)簇類所對(duì)應(yīng)的子空間。在每一個(gè)簇類中，賦予各維度屬性不同的權(quán)值，權(quán)值代表屬性對(duì)于簇類的相關(guān)程度。根據(jù)已有的研究成果，子空間聚類方法可被劃分為硬子空間聚類和軟子空間聚類兩大類［2］。硬子空間聚類方法在聚類過程中賦予簇類中各維度屬性的權(quán)值為0或1，用來表示屬性與該簇類不相關(guān)或相關(guān)。與硬子空間聚類相比，軟子空間聚類區(qū)別在于在聚類過程中賦予簇類中各維度屬性［0，1］區(qū)間的權(quán)值。與硬子空間聚類相比，軟子空間聚類不僅反映了屬性與簇是否相關(guān)，而且還反映了各相關(guān)屬性在相關(guān)程度上的差異［8］，因此，軟子空間聚類近年來在數(shù)據(jù)挖掘領(lǐng)域中是一個(gè)重要的研究課題［2，7，9－10］。許多新的軟子空間 聚 類 算 法，如EWKM［2］、FWKM［9］、FSC［10］已經(jīng)被提出并應(yīng)用到不同領(lǐng)域，它們的聚類性能也越來 越高。然而，這些 軟 子 空 間 聚 類 算 法［2，9－10］考慮更多的是對(duì)數(shù)據(jù)集劃分的優(yōu)化［11］，并沒有考慮對(duì)各簇類所在的子空間進(jìn)行優(yōu)化，在一定程度上降低了算法效率和聚類精確度。原因在于軟子空間聚類中，每一個(gè)簇類的成員一般是由算法發(fā)現(xiàn)的子空間和加權(quán)歐式距離共同確定的。因此，子空間的優(yōu)化對(duì)聚類算法的效果有著重要影響。

文中提出一種新的基于特征加權(quán)優(yōu)化的軟子空間聚類算法（Soft－subspace clustering based on feature optimization，SCFO），用于高維數(shù)據(jù)的聚類分析。SCFO算法優(yōu)點(diǎn)在于：在聚類過程中迭代地對(duì)數(shù)據(jù)集進(jìn)行劃分的同時(shí)優(yōu)化各個(gè)簇類所在的子空間，并且除了簇類數(shù)以外無需用戶額外輸入其它任何參數(shù)。通過在實(shí)際數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，與其它軟子空間聚類算法相比，SCFO算法能夠獲得更好的聚類效果。

1 相關(guān)研究

軟子空間聚類與傳統(tǒng)聚類方法不同，為了衡量屬性（特征）與簇類的相關(guān)性，軟子空間聚類在聚類過程中賦予簇類中的各維度屬性一個(gè)權(quán)值。通常，在一個(gè)簇類中的每一維屬性與簇類具有不同的相關(guān)性［2］，因此，在聚類過后各簇類所在的子空間可以通過特征權(quán)值來識(shí)別。軟子空間聚類就成為目前高維數(shù)據(jù)聚類分析的研究熱點(diǎn)［2，7，9－10］。

在詳細(xì)介紹相關(guān)工作之前，首先對(duì)全文所使用的符號(hào)進(jìn)行說明。文中，記DB＝｛x1，…，xi，…，xN｝為數(shù)據(jù)集，V＝｛vkj｝C×D為簇類中心矩陣，U＝｛uki｝C×N為隸屬度矩陣，W＝｛wkj｝C×D為權(quán)值矩陣。其中，C是簇類數(shù)，D是數(shù)據(jù)集中樣本點(diǎn)的維數(shù)，xij表示樣本xi的第j維屬性值（j＝1，2，…，D），vkj是第k個(gè)簇中心點(diǎn)的第j維屬性值，uki是第i個(gè)樣本對(duì)第k類簇的隸屬度，wkj表示第j維屬性與第k個(gè)簇類的相關(guān)程度，wkj的值越大代表相關(guān)性越強(qiáng)。

Gan［9］等提出了一種處理高維數(shù)據(jù)聚類的軟子空間聚類算法FSC。該算法定義了模糊權(quán)值，并將模糊權(quán)值引入到k－均值聚類算法的目標(biāo)函數(shù)中，進(jìn)而確定了以下目標(biāo)函數(shù)：

其中，ε0的引入是為了避免FSC算法在聚類過程中可能出現(xiàn)除以零的錯(cuò)誤，τ是模糊因子。對(duì)數(shù)據(jù)集DB進(jìn)行劃分后，F(xiàn)SC算法使用下式更新權(quán)值：

從上式可以看出，F(xiàn)SC算法的模糊權(quán)值更新方式類似于模糊k－均值聚類算法的模糊隸屬度的加權(quán)方法。同時(shí)，觀察上式可以發(fā)現(xiàn)在同一個(gè)簇類中，賦予每一維屬性的權(quán)值與該屬性上的數(shù)據(jù)分散程度成反比，某一維屬性上的數(shù)據(jù)越分散，其被賦予的權(quán)值越小，反之亦然。FSC算法首先初始化簇中心，然后迭代地更新權(quán)值矩陣W和聚類中心矩陣V，直到滿足結(jié)束條件。為了避免在權(quán)值計(jì)算中加入ε0，Jing［2］等提出了另一種軟子空間聚類算法EWKM，其目標(biāo)函數(shù)定義如下：

其中，目標(biāo)函數(shù)的第1項(xiàng)為簇內(nèi)緊湊度，第2項(xiàng)為權(quán)值熵；γ是用戶輸入的參數(shù)，其引入的目的是為了在聚類過程中平衡熵對(duì)權(quán)值的影響。假如參數(shù)γ值很大，各個(gè)簇類中的每一維度屬性被賦予的權(quán)值將基本相同。因此，通過熵的引入，EWKM算法能夠有效地控制簇類中各屬性被賦予的權(quán)值。但是從以上算法可以發(fā)現(xiàn)，這些算法在聚類過程中更多的是針對(duì)簇類的簇內(nèi)緊湊度問題，并未考慮對(duì)子空間進(jìn)行優(yōu)化，從而在一定程度上影響了算法的聚類精確度。

綜合FSC算法和EWKM算法，文中定義了衡量特征權(quán)值分布的新指標(biāo)，并與簇內(nèi)緊湊度相結(jié)合構(gòu)造了一個(gè)新的目標(biāo)函數(shù)，以此為基礎(chǔ)提出一個(gè)新的軟子空間聚類算法SCFO。新算法采用類似于k－均值的算法結(jié)構(gòu)，迭代地優(yōu)化目標(biāo)函數(shù)，以獲得更高的聚類精度。

2 SCFO算法

2.1 目標(biāo)優(yōu)化函數(shù)

在軟子空間聚類方法中關(guān)于特征加權(quán)有如下特點(diǎn)：在同一個(gè)簇類中，各維度屬性的權(quán)值與該維度屬性的數(shù)據(jù)分散程度成反比［2］，即某個(gè)維度上的數(shù)據(jù)越集中，則該維度屬性的權(quán)值越大，體現(xiàn)了該維度屬性對(duì)簇類越重要。因此，從一定程度上特征權(quán)值的大小反映了該屬性上數(shù)據(jù)的分散程度，而特征權(quán)值的分布越集中越體現(xiàn)了簇類所在的子空間越優(yōu)化［7］。在滿足wk1＋wk2＋…＋wkD＝1的條件下，文中給出如下公式，用于衡量特征權(quán)值的分布情況：

根據(jù)式（1）可知，特征權(quán)值分布越均勻，fwdk值越小。與大多數(shù)傳統(tǒng)聚類算法一樣，考慮各個(gè)屬性與簇類的重要程度都相同的情況下，即?j，j＝1，2，…，D，wkj＝1／D，fwdk獲得最小的值?；谑剑?），文中算法的目標(biāo)函數(shù)采用了類似EWKM算法的形式。構(gòu)造目標(biāo)函數(shù)具體如下：

其中，目標(biāo)函數(shù)的第1項(xiàng)是加權(quán)的簇內(nèi)緊湊度之和；系數(shù)rk用來平衡簇內(nèi)緊湊度和特征權(quán)值分布對(duì)目標(biāo)函數(shù)的影響。參考文獻(xiàn)［7］，文中將系數(shù)rk的值設(shè)置為：

上式中Xkj是引入的新記號(hào)，Xkj定義為：

利用拉格朗日乘子優(yōu)化方法最小化目標(biāo)函數(shù)JSCFO，獲得了SCFO算法隸屬度uki，聚類中心vkj和特征加權(quán)wkj的迭代計(jì)算公式，見定理1。

定理1 給定rk，最小化SCFO算法的優(yōu)化目標(biāo)函數(shù)JSCFO，當(dāng)且僅當(dāng)：

1）隸屬度uki的迭代計(jì)算公式為：

2）聚類中心vkj的迭代計(jì)算公式為：

3）特征加權(quán)wkj的迭代計(jì)算公式為：

式中：λk——拉格朗日乘子。

定理1的證明過程可以參考文獻(xiàn)［2，9－10］。

定理2 在區(qū)間（－MIN＿Xk，＋∞）內(nèi)，存在唯一的λk使式（5）成立。其中MIN＿Xk表示Xkj（j＝1，2，…，D）中的最小值。

證明 在滿足wk1＋wk2＋…＋wkD＝1的條件下，結(jié)合特征加權(quán)wkj的迭代計(jì)算式（4），獲得λk的約束方程如下：和，因此存在唯

基于上述約束方程，可證得λk在區(qū)間（－MIN＿Xk，＋∞）內(nèi)Ψ（λk）單 調(diào) 遞 減，且一的λk使得式（5）成立，從而定理2得證。此外，一般可以采用牛頓法［12］求解方程（5）。

2.2 SCFO算法過程和分析

SCFO算法根據(jù)式（2）～式（5）最小化目標(biāo)函數(shù)JSCFO，具體算法描述如下：

輸入：簇類個(gè)數(shù)C；隨機(jī)選擇C個(gè)初始聚類中心并設(shè)置所有的特征權(quán)值初始值均為1／D；

重復(fù)：

根據(jù)式（2），更新隸屬度矩陣U；

社區(qū)教育部門開展的非物質(zhì)文化遺產(chǎn)傳承與創(chuàng)新活動(dòng)采取線上、線下、線上與線下混合式、體驗(yàn)式的網(wǎng)絡(luò)直播、遠(yuǎn)程講堂與培訓(xùn)、非物質(zhì)文化遺產(chǎn)進(jìn)學(xué)校等多種方式，如下表。

根據(jù)式（3），更新簇類中心矩陣V；

根據(jù)式（5），利用牛頓法求解每個(gè)簇類對(duì)應(yīng)的拉格朗日乘子；

根據(jù)式（4），更新權(quán)值矩陣W；

算法結(jié)束：直到目標(biāo)函數(shù)值達(dá)到最小值或V和W在迭代過程中相鄰兩次的變化小于給定的閾值；

輸出：最終的聚類中心矩陣V和隸屬度矩陣U。

SCFO算法采用了類似于k－均值聚類的算法結(jié)構(gòu)，在聚類過程中額外增加了計(jì)算特征權(quán)值的步驟，并且對(duì)每個(gè)迭代步驟使用的更新公式進(jìn)行了重新定義，因此SCFO保留了k－均值聚類算法的收斂性。假設(shè)SCFO算法需要P次的循環(huán)迭代才能滿足結(jié)束條件，通過分析SCFO算法的每個(gè)執(zhí)行步驟，可以獲得算法的時(shí)間復(fù)雜度為O（KNDP）。因此，SCFO算法與k－均值聚類算法的時(shí)間復(fù)雜度相同。

3 實(shí)驗(yàn)結(jié)果與分析

為了檢驗(yàn)SCFO算法的性能，文中對(duì)SCFO算法和FSC［10］、EWKM［2］、FWKM［9］以及ASC［7］聚類算法進(jìn)行比較。對(duì)于這些算法的參數(shù)設(shè)置，這里采用各文獻(xiàn)的建議。例如，對(duì)于EWKM算法的γ，根據(jù)建議設(shè)定為0.5；FSC算法的τ根據(jù)文獻(xiàn)［10］設(shè)定為2.1；FWKM算法的β設(shè)定為1.5；SCFO算法與ASC算法一樣，除了簇類個(gè)數(shù)K，無須用戶輸入額外參數(shù)。實(shí)驗(yàn)計(jì)算機(jī)配置采用Intel?Core（TM）i5－3470CPU＠3.20GHz，4G內(nèi)存，仿真軟件為Eclipse3.5。

3.1 聚類性能指標(biāo)

為了評(píng)估聚類效果，文中采用互信息NMI［13］和Rand指數(shù)（RI）［14］兩個(gè)聚類性能指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià)，公式如下：

式中：K——聚類數(shù)；

n00——各樣本不屬于同一簇類并被劃分到不同聚類結(jié)果的樣本點(diǎn)數(shù)量；

n11——各樣本屬于同一簇類并被劃分到相同聚類結(jié)果的樣本點(diǎn)數(shù)量；

nij——屬于類i并被分配到簇類j的樣本數(shù)目；

ni——屬于類i的樣本數(shù)目；

nj——屬于簇j的樣本數(shù)目。

根據(jù)以上公式可知，RI和NMI這兩個(gè)指標(biāo)的值均落在區(qū)間［0，1］中，指標(biāo)值越大表示算法的聚類效果越好，反之亦然。當(dāng)上述兩個(gè)性能指標(biāo)的值均為1時(shí)，聚類算法將完全正確的識(shí)別出數(shù)據(jù)集中的每個(gè)簇類。

3.2 實(shí)驗(yàn)數(shù)據(jù)集

為了檢驗(yàn)SCFO算法的有效性和聚類精度，文中采用來自于UCI的7個(gè)數(shù)據(jù)集：Wisconsin Breast Cancer（WBC）、Waveform、Semeion、SPECT、Spambase、Wine和Mfeat。其中WBC和Wine這2個(gè)低維數(shù)據(jù)集主要用于評(píng)估聚類算法對(duì)低維數(shù)據(jù)集的兼容性。數(shù)據(jù)集的詳細(xì)信息見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集的詳細(xì)信息

3.3 實(shí)驗(yàn)結(jié)果聚類性能指標(biāo)

文中選取了UCI的7個(gè)數(shù)據(jù)集進(jìn)行對(duì)比測(cè)試。對(duì)于所有的實(shí)驗(yàn)數(shù)據(jù)集，文中使用最小最大規(guī)范化處理，使得實(shí)驗(yàn)數(shù)據(jù)集中的各屬性值均落在區(qū)間［0，1］中。同時(shí)，為了保證實(shí)驗(yàn)的公平性、代表性，避免極端情況的出現(xiàn)，每一個(gè)算法均獨(dú)立運(yùn)行20次，最后取20次實(shí)驗(yàn)結(jié)果的平均精度和方差，聚類結(jié)果分別見表2和表3。

表2 SCFO以及其它4種算法20次運(yùn)行的實(shí)驗(yàn)結(jié)果（RI指標(biāo)）

表3 SCFO以及其它4種算法20次運(yùn)行的實(shí)驗(yàn)結(jié)果（NMI指標(biāo)）

從表2和表3給出的聚類結(jié)果來看，顯然在UCI的7個(gè)數(shù)據(jù)集上，SCFO算法相比其它4種算法獲得了最好的聚類劃分結(jié)果；FSC、EWKM和FWKM算法的聚類質(zhì)量基本相同，而ASC的聚類質(zhì)量優(yōu)于FSC、EWKM和FWKM算法。這是因?yàn)锳SC與SCFO算法一樣，在聚類過程中不僅考慮了數(shù)據(jù)集劃分的優(yōu)化，而且對(duì)各個(gè)簇類所在的子空間也進(jìn)行了優(yōu)化。對(duì)比表2和表3，可以觀察到算法在某個(gè)數(shù)據(jù)集上獲得最高的RI值，但其對(duì)應(yīng)的NMI值卻不一定最高，即一個(gè)表現(xiàn)出高精度的聚類算法可能擁有很大的RI值，而可能沒有一個(gè)高的NMI值。因此，檢驗(yàn)算法的聚類性能通常需要不同的評(píng)價(jià)指標(biāo)來評(píng)估。

SCFO以及其它4種算法20次運(yùn)行的平均時(shí)間見表4。

表4 SCFO以及其它4種算法20次運(yùn)行的平均時(shí)間 s

表4記錄了SCFO、FSC、EWKM、FWKM以及ASC這5種算法在UCI的7個(gè)數(shù)據(jù)集上聚類所需要的平均運(yùn)行時(shí)間。對(duì)比SCFO和其它4種算法，可以發(fā)現(xiàn)新的基于特征加權(quán)優(yōu)化的軟子空間聚類算法SCFO并不會(huì)對(duì)算法的運(yùn)行時(shí)間帶來明顯影響。我們注意到SCFO算法和ASC算法在Mfeat和Semeion這兩個(gè)高維數(shù)據(jù)集上的運(yùn)行時(shí)間大于其它3種聚類算法，這是因?yàn)镾CFO算法和ASC算法在聚類過程中增加了求解各個(gè)簇類對(duì)應(yīng)的拉格朗日乘子的步驟。該步驟導(dǎo)致了算法在高維數(shù)據(jù)集上需要耗費(fèi)更多的運(yùn)算時(shí)間，但其有效地增強(qiáng)了算法的自適應(yīng)能力，一定程度上提高了算法的聚類精度。

4 結(jié) 語

提出了一種新的基于特征加權(quán)優(yōu)化的軟子空間聚類算法SCFO，用以解決高維數(shù)據(jù)的聚類問題。與傳統(tǒng)的軟子空間聚類算法相比，SCFO算法在聚類過程中考慮了數(shù)據(jù)集劃分和各簇類所在子空間兩方面的優(yōu)化，除了簇類個(gè)數(shù)K，SCFO算法無需用戶預(yù)先輸入其它任何參數(shù)。通過在UCI的7個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，SCFO算法相比于FSC、EWKM、FWKM和ASC，能夠獲得更好的聚類質(zhì)量。為了能夠進(jìn)一步獲得更好的聚類效果，今后的研究將考慮對(duì)SCFO算法平衡目標(biāo)函數(shù)中的前后兩項(xiàng)的系數(shù)進(jìn)行優(yōu)化。

［1］ Moreno－Hagelsieb G，Wang Z，Walsh S，et al.Phylogenomic clustering for selecting non－redundant genomes for comparative genomics［J］.Bioinformatics，2013，29（7）：947－949.

［2］ Jing L，Ng M K，Huang J Z.An entropy weighting k－means algorithm for subspace clustering of highdimensinoal sparese data［J］.IEEE Transactions on Knowledge and Data Engineering，2007，19（8）：1－16.

［3］ Tang L，Liu H，Zhang J.Identifying evolving groups in dynamic multimode networks［J］.IEEE Transactions on Knowledge and Data Engineering，2012，24（1）：72－85.

［4］ Huang J Z，Ng M K，Rong H，et al.Automated variable weighting in k－means type clustering［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（5）：657－668.

［5］ Parsons L，Haque E，Liu H.Subspace clustering for high dimensional data：a review［J］.ACM SIGKDD Explorations Newsletter，2004，6（1）：90－105.

［6］ Aggarwal C C，Wolf J L，Yu P S，et al.Fast algorithm for projected clustering［C］／／Proceeding of ACM SIGMOD.1999：61－72.

［7］ 陳黎飛，郭躬德，姜青山.自適應(yīng)的軟子空間聚類算法［J］.軟件學(xué)報(bào)，2010，21（10）：2513－2523.

［8］ 畢志升，王甲海，印鑒.基于差分演化算法的軟子空間聚類［J］.計(jì)算機(jī)學(xué)報(bào)，2012，35（10）：2116－2128.

［9］ Jing L，Ng M K，Xu J，et al.On the performance of feature weighting k－means for text subspace clustering［C］／／Proceeding of WAIM.2005：502－512.

［10］ Gan G，Wu J，Yang Z.Fuzzy subspace algorithm for clustering high dimensional data［C］／／Proceeding of ADMA.2006：271－278.

［11］ Chu Y H，Chen Y J，Yang D N，et al.Reducing redundancy in subspace clustering［J］.IEEE Transactions on Knowledge and Data Engineering，2009，21（10）：1432－1446.

［12］ Xue Y.Optimization theory and method［M］.Beijing：Beijing University of Technology Press，2001.

［13］ Liu J，Mohammed J，Carter J，et al.Distancebased clustering of CGH data［J］.Bioinformatics，2006，22（16）：1971－1978.

［14］ Rand W M.Objective criteria for the evaluation of clustering methods［J］.Journal of the American Statistical Association，1971，66（336）：846－850.