金利英, 趙升噸

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

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

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

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

1　iMWK-HD算法

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

(1)

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

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

1.2　混合測(cè)量

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

(2)

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

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

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

(3)

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

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

(4)

(5)

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

β∈{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í)驗(yàn)設(shè)計(jì)和結(jié)果分析

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

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

2.1　實(shí)驗(yàn)數(shù)據(jù)和評(píng)估指標(biāo)

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

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

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

2.2　實(shí)驗(yàn)結(jié)果和分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(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)于另外兩種算法,說(shuō)明iMWK-HD算法聚類(lèi)結(jié)果的穩(wěn)定性好。這是因?yàn)閕MWK-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ù)分布情況

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

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

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

3　結(jié)　論

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

參考文獻(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),徐亮,馬永浩,等.實(shí)驗(yàn)研究類(lèi)螺紋孔旋流沖擊射流的冷卻特性.2018,52(1):8-13.[doi:10.7652/xjtuxb201801 002]

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

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

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

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

程傳奇,郝向陽(yáng),李建勝,等.融合改進(jìn)A*算法和動(dòng)態(tài)窗口法的全局動(dòng)態(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]

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

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