混合測量子空間聚類算法的研究

金利英, 趙升噸

(西安交通大學(xué)機(jī)械工程學(xué)院, 710049, 西安)

子空間聚類算法是模式識別和數(shù)據(jù)挖掘等應(yīng)用領(lǐng)域的重要工具,隨著新技術(shù)的高速發(fā)展,應(yīng)用環(huán)境不斷變化,大規(guī)模數(shù)據(jù)與復(fù)雜結(jié)構(gòu)數(shù)據(jù)對子空間聚類算法的需求越來越緊迫。迄今為止,已開發(fā)出許多聚類算法[1-2],以實現(xiàn)數(shù)據(jù)聚類的任務(wù),這些算法在如何定義集群以及如何識別集群方面有很大的不同。K-means算法是最經(jīng)典且應(yīng)用最廣的聚類算法之一[3],但對聚類中心的初始化非常敏感,影響聚類結(jié)果和收斂速度。Huang等在K-means算法的基礎(chǔ)上提出了權(quán)重K-means算法(WK-means)[4],為每個特征分配一個權(quán)重,特征權(quán)重與特征尺度因子相關(guān)[5]。使用閔可夫斯基距離自動計算每個集群的特征權(quán)重,以確保這些權(quán)重可以看作是特征調(diào)節(jié)因子。

現(xiàn)有的大多數(shù)子空間聚類算法僅使用一個距離函數(shù)來評估各個樣本之間的距離,該距離函數(shù)難以處理具有復(fù)雜內(nèi)部結(jié)構(gòu)的數(shù)據(jù)集。通過特征之間權(quán)重方向旋轉(zhuǎn)特征空間可進(jìn)一步提高聚類性能,在向量空間模型中[6],余弦相異性比歐式距離更重要。在特征空間(ESCHD)中[7],余弦相異性可提高軟子空間聚類的性能。

受iMWK-means和ESCHD算法的啟發(fā),本文提出了混合測量子空間聚類算法(iMWK-HD)。該算法將余弦相異性引入到距離函數(shù)中,使閔可夫斯基指數(shù)與分配特征權(quán)重指數(shù)相符,構(gòu)造新的目標(biāo)函數(shù)。使用該目標(biāo)函數(shù)推導(dǎo)迭代過程中更新規(guī)則,促進(jìn)特征空間的擴(kuò)展、收縮和旋轉(zhuǎn),iMWK-HD算法可提高聚類精度和聚類結(jié)果的穩(wěn)定性。

1　iMWK-HD算法

1.1　閔可夫斯基距離和智能K-means算法初始化類中心

(1)

式中:β為用戶定義的參數(shù),表示權(quán)重對距離貢獻(xiàn)的影響率。d(xi,xj)因β值的不同而變化,指數(shù)β≠2不再是特征比例因子。Huang等擴(kuò)展了相應(yīng)的閔可夫斯基測量[4],用于測量距離,以確保閔可夫斯基指數(shù)與特征權(quán)重指數(shù)一致。

智能K-means初始化[8](iK-means)是在運(yùn)行K-means算法之前找出異常集群,即對數(shù)據(jù)集進(jìn)行全局加權(quán)距離的計算并排序,取最大距離樣本點為異常集群,將其設(shè)置為初始類中心,在迭代過程中找出距離它最近的樣本點,然后從數(shù)據(jù)集中依次取出;在剩余數(shù)據(jù)集里取距離最遠(yuǎn)的樣本為初始化類中心,在迭代過程中找出距離它最近的樣本點,然后從這個數(shù)據(jù)集里移出;依次類推,直到剩余數(shù)據(jù)集為空,之后選取樣本點個數(shù)最多的異常簇的異常集群為類中心。

1.2　混合測量

基于距離測量準(zhǔn)則,在處理高維樣本點時會出現(xiàn)維數(shù)災(zāi)難的情況[9],影響聚類結(jié)果的穩(wěn)定性。將余弦相異性代入優(yōu)化目標(biāo)函數(shù)中,結(jié)合距離計算樣本點之間的距離,可促進(jìn)特征空間轉(zhuǎn)換,樣本點xi和第j維k類中心vk之間的距離定義為

(2)

混合測量參數(shù)較少、易于實現(xiàn),可控制數(shù)據(jù)集在特征空間中的形狀、大小和方向,能減小冗余和無關(guān)特征對數(shù)據(jù)集的影響,進(jìn)而區(qū)分特征在不同子空間中的權(quán)重大小,提高全局搜索能力。

1.3　目標(biāo)函數(shù)設(shè)計

目標(biāo)函數(shù)是評估聚類性能的重要指標(biāo),直接影響算法的搜索方向和收斂速度。假設(shè)有N個M維數(shù)據(jù)集X={X1,X2,…,XN},第i個樣本點表示為Xi=(xi1,xi2,…,xiM);聚類中心矩陣V={v1,v2,…,vC},C是N個數(shù)據(jù)集劃分類數(shù)。利用混合測量求解目標(biāo)函數(shù)最小值,定義為

(3)

式中:矩陣V=[vkj](1≤k≤C,1≤j≤M)為第k類在第j維特征上的類中心值;集群U=[uik](1≤i≤N,1≤k≤C)為第i個樣本對第k類的隸屬度;矩陣W=[wjk](1≤j≤M,1≤k≤C)為第j維特征對第k類的重要度。

iMWK-HD算法優(yōu)化目標(biāo)函數(shù),矩陣U、W的最優(yōu)解可由下式給出,即

(4)

(5)

矩陣V的求解可由文獻(xiàn)[5]中iMWK-means算法進(jìn)行迭代更新。式(3)的無約束最小化為

β∈{1.2,2.0,2.3,2.7,3.0,4.9},η∈[0,10],ε=10-5,G=500

iK-means initializeVandWwithwjk=1/M

fort=1:G

UpdataUt+1according to (4) withWtandVt;

UpdataVt+1according toWtandUt+1;

UpdataWt+1according to (5) withUt+1and

Vt+1;

Calculate the objective functionJ(Ut+1,Vt+1,Wt+1) with (3);

if |J(Ut+1,Vt+1,Wt+1)-J(U,V,W)|<εbreak;

End for

OutputWt+1,Vt+1andUt+1。

2　實驗設(shè)計和結(jié)果分析

實驗環(huán)境為Intel(R) Core(TM) i3-4170 CPU,Windows7,軟件開發(fā)平臺是Matlab 13.0。為驗證iMWK-HD算法有效性,與現(xiàn)有的iK-means,iWK-means和iMWK-means算法進(jìn)行對比。

通過以上對于孟子武德思想的分析與歷史經(jīng)驗的側(cè)證，我們可以看到，孟子以“仁者無敵”為核心的武德觀，因其精神化理想化的趨向和立意的高標(biāo)，在國家國際的層面無法得到落實而為荀子所倡的武德原則所取代。而至于共同體與個人的層面，因具有共同追求或現(xiàn)實制度作為基本保障，孟子的武德思想煥發(fā)了生命力，具有無窮的魅力。孟子將直接的暴力置換為王霸之辯、天爵人爵之辯、批判精神、大丈夫人格與浩然之氣，面對沖突和矛盾，拒絕茍且或殘暴而指出向上一路。孟子亦被譽(yù)為“中國歷史上最有使命感的文化斗士，最有生命力的衛(wèi)道圣雄”[12](P365)。

2.1　實驗數(shù)據(jù)和評估指標(biāo)

選取UCI數(shù)據(jù)庫[10]中Wine、Hepatitis、Australian、Liver、Wave、Sonar、Musk這7個數(shù)據(jù)集來進(jìn)行對比實驗,其基本信息如表1所示。在實驗中,使用精確度ACC[11]和RI[12]指標(biāo)來評估聚類結(jié)果的性能,RI定義為

式中:T為在同一類的一對樣本點被分到同一類內(nèi);E為不在同一類的一對樣本點被分到不同的類里;F為不在同一類的一對樣本點被分到同一類內(nèi);P為在同一類的一對樣本點被分到不同類里。ACC、RI取值范圍為[0,1],數(shù)值越接近1,說明聚類性能越好。

表1　數(shù)據(jù)描述

2.2　實驗結(jié)果和分析

算法對7個數(shù)據(jù)集聚類的最優(yōu)精度、最優(yōu)解如表2、表3所示。iMWK-HD算法和iMWK-means算法之間是閔可夫斯基指數(shù)β取相同值時對數(shù)據(jù)集進(jìn)行實驗比較,表中平衡系數(shù)η為iMWK-HD算法獲得最優(yōu)實驗結(jié)果時的取值。

由表2、表3可知:iMWK-HD算法在7個數(shù)據(jù)集上均獲得最優(yōu)的ACC、RI,高出其他3種算法數(shù)個百分點;在聚類結(jié)果的穩(wěn)定性、聚類精確度上,iMWK-HD算法更具優(yōu)勢。這是因為本文將閔可夫斯基距離、余弦相結(jié)合構(gòu)成新的目標(biāo)函數(shù),使其更好評價特征子集的質(zhì)量,能更好找到子空間的內(nèi)部結(jié)構(gòu),促進(jìn)樣本在特征空間轉(zhuǎn)換,提高全局搜索能力,從而獲得更好的聚類結(jié)果。

表2　算法對7個數(shù)據(jù)集聚類的最優(yōu)精度

表3　算法對7個數(shù)據(jù)集聚類的最優(yōu)解

β、η是iMWK-HD算法的重要參數(shù),對于大規(guī)模數(shù)據(jù)Wave、高維數(shù)據(jù)Musk,在β取不同值時實驗獲得的ACC隨η的變化趨勢如圖1、圖2所示。

圖1　iMWK-HD算法在β=1.2,2.0,2.3時的聚類結(jié)果

圖2　iMWK-HD算法在β=1.2,2.0,3.0,4.9時的聚類結(jié)果

由圖1中可知,當(dāng)β=1.2,2.0時,ACC隨著平衡系數(shù)η的不同取值而變化,且絕大多數(shù)ACC優(yōu)于未引入余弦時的聚類結(jié)果,說明引入余弦可增強(qiáng)算法的魯棒性;當(dāng)β=2.3且η=3,4,6,7,9,10時,ACC低于η=0時的值,說明對大規(guī)模數(shù)據(jù)而言,β在2.3以內(nèi)引入余弦能很好地調(diào)節(jié)特征權(quán)重因子,促進(jìn)特征空間轉(zhuǎn)換,從而提高聚類精確度;當(dāng)η=0且β分別取1.2、2.0、2.3時,實驗獲得的ACC分別為45.1%、51.1%、51.3%;當(dāng)η=1時,ACC分別為50.5%、68%、55.8%;當(dāng)η=2時,ACC分別為53.7%、50.7%、65.4%;當(dāng)η取定值時,在β取值范圍內(nèi),實驗獲得的ACC與β取值無關(guān),這說明余弦的引入與β不沖突。

由圖2中可知,當(dāng)β=1.2時,ACC隨著η的不同取值而變化,且當(dāng)η=3時,ACC均小于η=0時的值,說明余弦的引入在β=1.2時的聚類結(jié)果不穩(wěn)定。當(dāng)β=2.0,3.0,4.9時,大部分ACC優(yōu)于未引入余弦時的聚類結(jié)果,對于高維數(shù)據(jù),β取值大于2.0時余弦的引入能很好調(diào)節(jié)特征權(quán)重因子,促進(jìn)特征空間轉(zhuǎn)換,從而提高聚類ACC和算法的魯棒性。因此,iMWK-HD算法在原子空間聚類算法參數(shù)下,有且僅增加一個控制參數(shù)η,能最大程度保證算法在高維數(shù)據(jù)中的聚類精度和聚類結(jié)果的穩(wěn)定性。

表4　Wave數(shù)據(jù)集精確度ACC

表5　Wave數(shù)據(jù)集RI

由表4、5可知,當(dāng)β=1.2,2.0且η=0,即未引入余弦時,iWK-means算法取得ACC最優(yōu)值,但iMWK-HD算法的ACC與最優(yōu)結(jié)果相差不大,而引入余弦時,iMWK-HD算法的ACC大部分優(yōu)于iWK-means和iMWK-means算法。當(dāng)β=2.3且η=0時,iMWK-HD和iMWK-means算法的ACC相同;而引入余弦時,iMWK-HD算法的最優(yōu)值高出iWK-means和iMWK-means算法分別為24.24%、24.1%,說明iMWK-HD算法具有較強(qiáng)魯棒性和較高聚類精度。ACC所示的最佳聚類性能并不總是與RI表示一致,因此有必要對不同指標(biāo)聚類算法的性能進(jìn)行評估。

表6　Msuk數(shù)據(jù)集精確度ACC

表7　Msuk數(shù)據(jù)集RI

由表6可知,當(dāng)η=0,即未引入余弦時,iMWK-HD和iMWK-means算法在β取不同值時ACC、RI均相同;當(dāng)引入余弦時,iMWK-HD算法在大多數(shù)情況下的實驗結(jié)果均優(yōu)于iMWK-means和iWK-means算法,只有少數(shù)實驗結(jié)果低于它們,且實驗結(jié)果相差不大,說明本文所提iMWK-HD算法具有較強(qiáng)魯棒性。Musk數(shù)據(jù)雖擁有較高維數(shù),iMWK-HD算法也能有效地提取對應(yīng)維數(shù)信息,再一次體現(xiàn)出iMWK-HD算法的聚類結(jié)果穩(wěn)定性好、聚類精度高的優(yōu)點。

(a)原始數(shù)據(jù)分配　　　(b)iMWK-HD算法

(c)iMWK-means算法　　(d)iWK-means算法圖3　　　　Wave數(shù)據(jù)集中3種算法根據(jù)特征權(quán)重進(jìn)行轉(zhuǎn)換的數(shù)據(jù)分布情況

3種算法根據(jù)特征權(quán)重進(jìn)行轉(zhuǎn)換的數(shù)據(jù)分布情況如圖3、圖4所示。由圖3、圖4可知,集群之間的重疊較少,在總體性能上優(yōu)于另外兩種算法,說明iMWK-HD算法聚類結(jié)果的穩(wěn)定性好。這是因為iMWK-HD算法的目標(biāo)函數(shù)中引入了余弦相異性,使特征權(quán)重在特征空間不僅能擴(kuò)展、收縮,還能旋轉(zhuǎn),iMWK-HD算法能有效提高解的質(zhì)量。

(a)原始數(shù)據(jù)分配　　　(b)iMWK-HD算法

(c)iMWK-means算法　　(d)iWK-means算法圖4　Musk數(shù)據(jù)集中數(shù)據(jù)分布情況

對比實驗結(jié)果說明了本文所提iMWK-HD算法的魯棒性及聚類結(jié)果的穩(wěn)定性。子空間聚類算法能更好發(fā)現(xiàn)子空間的內(nèi)部結(jié)構(gòu),展現(xiàn)良好的聚類結(jié)果。對于Wine數(shù)據(jù),各個子空間聚類算法的內(nèi)部結(jié)構(gòu)如表8所示,將其各維標(biāo)上對應(yīng)編號。由表8中前6位特征重要性排序可知,所得各個數(shù)據(jù)簇的特征排列順序在每個子空間聚類算法中有所不同,也可在其他數(shù)據(jù)集中得到類似發(fā)現(xiàn),這種發(fā)現(xiàn)子空間的能力可提高聚類有效性。

表8　Wine數(shù)據(jù)集上的特征重要性排序

綜上對比實驗結(jié)果,分析iMWK-HD算法最優(yōu)的原因:①初始化階段使用智能K-means算法求解聚類中心點,解決了隨機(jī)選取類中心導(dǎo)致若干聚類合并及正確選擇類數(shù)的問題;②混合測量導(dǎo)出樣本與中心點的距離,解決了特征空間旋轉(zhuǎn)問題;③利用拉格朗日乘子求解新的隸屬度和特征權(quán)重迭代更新公式,保證了類中心的穩(wěn)定性,從而促進(jìn)特征空間轉(zhuǎn)換,獲取有效的聚類結(jié)果。實驗結(jié)果驗證了iMWK-HD算法的優(yōu)越性。

3　結(jié)　論

本文提出了一種混合測量子空間聚類算法,該算法是在iMWK-means框架下,將余弦相異性引入到子空間聚類的目標(biāo)函數(shù)中,與閔氏距離相結(jié)合,構(gòu)造了新的目標(biāo)函數(shù),該目標(biāo)函數(shù)控制參數(shù)少,易于實現(xiàn);利用拉格朗日乘子求解樣本點新的隸屬度和特征權(quán)重迭代更新距陣,實現(xiàn)特征權(quán)重因子自動調(diào)節(jié),促進(jìn)特征空間轉(zhuǎn)換,從而有利于隸屬度矩陣U的劃分和類中心矩陣V的精準(zhǔn)度,最終獲取樣本點的最優(yōu)聚類結(jié)果,提高聚類性能。實驗結(jié)果表明,與iK-means、iWK-means和iMWK-means三種算法相比,iMWK-HD算法聚類結(jié)果穩(wěn)定性好,聚類精確度高。

參考文獻(xiàn):

[1]PAN Y, WANG J, DENG Z. Alternative soft subspace clustering algorithm [J]. Journal of Information & Computational Science, 2013, 10: 3615-3624.

[2]CHEN X, YE Y, XU X, et al. A feature group weighting method for subspace clustering of high-dimensional data [J]. Pattern Recognition, 2012, 45: 434-446.

[3]MACQUEEN J. Some methods for classification and analysis of multivariate observations [J]. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1967, 1: 281-297.

[4]HUANG Z, NG M K, RONG H, et al. Automated variable weighting in k-means type clustering [J]. IEEE Transactions on Pattern Analysis and Machine Learning, 2005, 27(5): 657-668.

[5]RENATO C D, MIRKIN B. Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering [J]. Pattern Recognition, 2012, 45: 1061-1075.

[6]KIM D. Group-theoretical vector space model [J]. International Journal of Computer Mathematics, 2015, 92(8): 1536-1550.

[7]WANG L, HAO Z, CAI R, et al. Enhanced soft subspace clustering through hybrid dissimilarity [J]. Journal of Intelligent & Fuzzy Systems, 2015, 29: 1395-1405.

[8]CHIANG M M, MIRKIN B. Intelligent choice of the number of clusters in k-means clustering: an experimental study with different cluster spreads [J]. Journal of Classification, 2010, 27(1): 1-38.

[9]PARSONS L, HAQUE E, LIU H. Subspace clustering for high dimensional data: a review [J]. ACM Sigkdd Explorations Newsletter, 2004, 6(1): 90-105.

[10] DENG Z, CHOI K S, CHUNG F L, et al. Enhanced soft subspace clustering integrating within-cluster and between-cluster information [J]. Pattern Recognition, 2010, 43(3): 767-781.

[11] HUANG J Z, XU J, NG M, et al. Weighting method for feature selection in k-means [J]. Computational Methods of Feature Selection, Chapman & Hall/CRC, 2007, 193-209.

[12] RAND W M. Objective criteria for the evaluation of clustering methods [J]. Journal of the American Statistical Association, 1971, 66: 846-850.

[本刊相關(guān)文獻(xiàn)鏈接]

蘭進(jìn),徐亮,馬永浩,等.實驗研究類螺紋孔旋流沖擊射流的冷卻特性.2018,52(1):8-13.[doi:10.7652/xjtuxb201801 002]

韓樹楠,張旻,李歆昊.高容錯(2,1,m)卷積碼快速盲識別方法.2017,51(12):28-34.[doi:10.7652/xjtuxb201712005]

姜洪權(quán),王崗,高建民,等.一種適用于高維非線性特征數(shù)據(jù)的聚類算法及應(yīng)用.2017,51(12):49-55.[doi:10.7652/xjtuxb201712008]

曹巖,韋婉鈺,喬虎,等.采用設(shè)計結(jié)構(gòu)矩陣的突發(fā)事件擴(kuò)散預(yù)測及建模方法.2017,51(12):68-75.[doi:10.7652/xjtuxb 201712011]

王瑞琴,高炎,晏鑫,等.燃?xì)馔钙轿簿夐_縫區(qū)冷卻性能的非定常研究.2017,51(12):98-103.[doi:10.7652/xjtuxb201712 015]

程傳奇,郝向陽,李建勝,等.融合改進(jìn)A*算法和動態(tài)窗口法的全局動態(tài)路徑規(guī)劃.2017,51(11):137-143.[doi:10.7652/xjtuxb201711019]

黃興旺,曾學(xué)文,郭志川,等.采用改進(jìn)二進(jìn)制蝙蝠算法的任務(wù)調(diào)度算法.2017,51(10):65-70.[doi:10.7652/xjtuxb2017 10011]

舒帆,屈丹,張文林,等.采用長短時記憶網(wǎng)絡(luò)的低資源語音識別方法.2017,51(10):120-127.[doi:10.7652/xjtuxb2017 10020]

曹衛(wèi)權(quán),褚衍杰,李顯.針對機(jī)器學(xué)習(xí)中殘缺數(shù)據(jù)的近似補(bǔ)全方法.2017,51(10):142-148.[doi:10.7652/xjtuxb201710 023]