莊景暉

（漳州職業(yè)技術(shù)學(xué)院 計算機(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)對數(shù)據(jù)集進(jìn)行劃分，進(jìn)而形成多個簇類，劃分的結(jié)果使得簇內(nèi)的樣本盡可能相似，不同簇間的樣本盡可能相異［4］。現(xiàn)今，隨著信息技術(shù)的飛速發(fā)展，數(shù)據(jù)的采集變得更加方便與迅速，也因此導(dǎo)致了人們獲得的數(shù)據(jù)集變得更大、更復(fù)雜。與低維數(shù)據(jù)相比，在高維數(shù)據(jù)空間中通常存在著許多并不相關(guān)的屬性［5］，同時還存在著“維度效應(yīng)”的問題，從而導(dǎo)致多數(shù)傳統(tǒng)聚類分析方法無法有效地聚類分析高維數(shù)據(jù)。為了解決這類問題，國內(nèi)外研究人員針對高維數(shù)據(jù)的分析提出了很多的聚類方法［6］，其中的子空間聚類就是一類代表性的方法。

子空間聚類是指在高維數(shù)據(jù)空間中挖掘存在于某些低維子空間中簇類的技術(shù)［7］。它將數(shù)據(jù)集劃分并形成多個簇類，從中尋找出數(shù)據(jù)集中各個簇類所對應(yīng)的子空間。在每一個簇類中，賦予各維度屬性不同的權(quán)值，權(quán)值代表屬性對于簇類的相關(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)域中是一個重要的研究課題［2，7，9－10］。許多新的軟子空間 聚 類 算 法，如EWKM［2］、FWKM［9］、FSC［10］已經(jīng)被提出并應(yīng)用到不同領(lǐng)域，它們的聚類性能也越來 越高。然而，這些 軟 子 空 間 聚 類 算 法［2，9－10］考慮更多的是對數(shù)據(jù)集劃分的優(yōu)化［11］，并沒有考慮對各簇類所在的子空間進(jìn)行優(yōu)化，在一定程度上降低了算法效率和聚類精確度。原因在于軟子空間聚類中，每一個簇類的成員一般是由算法發(fā)現(xiàn)的子空間和加權(quán)歐式距離共同確定的。因此，子空間的優(yōu)化對聚類算法的效果有著重要影響。

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

1 相關(guān)研究

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

在詳細(xì)介紹相關(guān)工作之前，首先對全文所使用的符號進(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ù)集中樣本點的維數(shù)，xij表示樣本xi的第j維屬性值（j＝1，2，…，D），vkj是第k個簇中心點的第j維屬性值，uki是第i個樣本對第k類簇的隸屬度，wkj表示第j維屬性與第k個簇類的相關(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)除以零的錯誤，τ是模糊因子。對數(shù)據(jù)集DB進(jìn)行劃分后，F(xiàn)SC算法使用下式更新權(quán)值：

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

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

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

2 SCFO算法

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

在軟子空間聚類方法中關(guān)于特征加權(quán)有如下特點：在同一個簇類中，各維度屬性的權(quán)值與該維度屬性的數(shù)據(jù)分散程度成反比［2］，即某個維度上的數(shù)據(jù)越集中，則該維度屬性的權(quán)值越大，體現(xiàn)了該維度屬性對簇類越重要。因此，從一定程度上特征權(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)聚類算法一樣，考慮各個屬性與簇類的重要程度都相同的情況下，即?j，j＝1，2，…，D，wkj＝1／D，fwdk獲得最小的值?；谑剑?），文中算法的目標(biāo)函數(shù)采用了類似EWKM算法的形式。構(gòu)造目標(biāo)函數(shù)具體如下：

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

上式中Xkj是引入的新記號，Xkj定義為：

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

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

1）隸屬度uki的迭代計算公式為：

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

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

式中：λ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的迭代計算式（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，具體算法描述如下：

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

重復(fù)：

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

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

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

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

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

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

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

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

3 實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

3.2 實驗數(shù)據(jù)集

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

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

3.3 實驗結(jié)果聚類性能指標(biāo)

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

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

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

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

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

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

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

4 結(jié) 語

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

［8］ 畢志升，王甲海，印鑒.基于差分演化算法的軟子空間聚類［J］.計算機(jī)學(xué)報，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.