基于PCA的高維多目標(biāo)優(yōu)化可視化方法

劉 廣,陳自郁

(重慶大學(xué)計(jì)算機(jī)學(xué)院,重慶400044)

基于PCA的高維多目標(biāo)優(yōu)化可視化方法

劉 廣,陳自郁

(重慶大學(xué)計(jì)算機(jī)學(xué)院,重慶400044)

高維多目標(biāo)優(yōu)化問(wèn)題的高維解集由于目標(biāo)和解的個(gè)數(shù)眾多,對(duì)其可視化較為困難。針對(duì)上述問(wèn)題,結(jié)合降維和非降維數(shù)據(jù)分析技術(shù),提出一種高維多目標(biāo)優(yōu)化的可視化方法。該方法對(duì)高維多目標(biāo)算法運(yùn)行后的一組解集進(jìn)行預(yù)處理,運(yùn)用主成分分析方法分析數(shù)據(jù)特征,獲取轉(zhuǎn)換后的數(shù)據(jù)及其對(duì)應(yīng)的貢獻(xiàn)率。按照貢獻(xiàn)率由大到小的順序調(diào)整轉(zhuǎn)換后的數(shù)據(jù)列順序;利用主成分貢獻(xiàn)率求解轉(zhuǎn)換后數(shù)據(jù)的行間距離,運(yùn)行分級(jí)聚類算法并對(duì)轉(zhuǎn)換后的數(shù)據(jù)按行排序,重新組織數(shù)據(jù),將最終的結(jié)果用熱圖顯示。實(shí)驗(yàn)結(jié)果表明,該方法既能使用戶明確轉(zhuǎn)換后每個(gè)目標(biāo)所占的貢獻(xiàn)率,又能取得較滿意的視覺(jué)效果,便于用戶理解數(shù)據(jù)的整體分布并做出決策。

主成分分析;熱圖;高維多目標(biāo)優(yōu)化;可視化;分級(jí)聚類;降維

1 概述

多目標(biāo)優(yōu)化問(wèn)題是使多個(gè)目標(biāo)在給定的區(qū)域內(nèi)盡可能達(dá)到最佳的優(yōu)化問(wèn)題,其在工程應(yīng)用等非常復(fù)雜的實(shí)際問(wèn)題中的應(yīng)用非常普遍,因此解決多目標(biāo)優(yōu)化問(wèn)題具有重要的實(shí)際和科研價(jià)值[1]。

當(dāng)多目標(biāo)優(yōu)化問(wèn)題的目標(biāo)個(gè)數(shù)少于3個(gè)時(shí),已經(jīng)有一系列非常有效且成熟的多目標(biāo)優(yōu)化算法。當(dāng)多目標(biāo)的個(gè)數(shù)增加到4個(gè)及以上時(shí),通常被稱為高維多目標(biāo)優(yōu)化問(wèn)題,目標(biāo)個(gè)數(shù)的增加對(duì)多目標(biāo)優(yōu)化算法帶來(lái)了極大的困難。主要表現(xiàn)在:(1)目標(biāo)個(gè)數(shù)的增加使得種群中非支配解的個(gè)數(shù)指數(shù)級(jí)增加,極大地削弱了基于Pareto支配進(jìn)行排序與選擇的效果[2];(2)增加了多目標(biāo)算法的計(jì)算復(fù)雜度和難度; (3)高維多目標(biāo)的最優(yōu)解集為其可視化制造了困難,影響決策者的最終決策。

對(duì)于高維多目標(biāo)的可視化問(wèn)題,由于人類認(rèn)知能力的局限性,不能直接觀察出來(lái)數(shù)據(jù)之間的沖突和冗余信息,因此需要采用可視化技術(shù),找出數(shù)據(jù)之間的關(guān)系及特征,并對(duì)其進(jìn)行顯示?？梢暬夹g(shù)為決策者觀察分析和理解數(shù)據(jù)及做出最終的決策,提供了極大的方便。高維多目標(biāo)可視化技術(shù)分為兩部分:數(shù)據(jù)分析和數(shù)據(jù)顯示。

數(shù)據(jù)顯示是指根據(jù)數(shù)據(jù)分析后的結(jié)果,采用合適的顯示工具,將數(shù)據(jù)呈現(xiàn)給決策者。目前數(shù)據(jù)顯示的工具非常多,如熱圖[3]、平行坐標(biāo)系[4-7]、面向像素技術(shù)、Chernoff-face圖標(biāo)顯示技術(shù)等。其中,平行坐標(biāo)系方法簡(jiǎn)單易用,對(duì)較少數(shù)據(jù),效果較好,但當(dāng)數(shù)據(jù)量大、數(shù)據(jù)維度很高時(shí),會(huì)使折線重疊,影響顯示效果,干擾決策者的決策。

相比之下,熱圖的顯示方式,直觀準(zhǔn)確,顯示的數(shù)據(jù)量大,但顯示的效果要依賴于事先對(duì)數(shù)據(jù)的良好組織。而面向像素的技術(shù)將每一個(gè)數(shù)據(jù)項(xiàng)的數(shù)值對(duì)應(yīng)于一個(gè)帶顏色的屏幕像素,每個(gè)屬性的所有數(shù)據(jù)在一個(gè)獨(dú)立的窗口顯示。與熱圖類似,其主要問(wèn)題是在屏幕上怎樣排列這些像素點(diǎn)。還有一種很獨(dú)特的顯示技術(shù)Chernoff-face圖標(biāo)顯示技術(shù),將一個(gè)數(shù)據(jù)條(包含所有屬性)所有的維映射在一張臉上,臉上每個(gè)器官代表每個(gè)屬性,其充分地利用了臉的豐富表情特征,但是能表示的數(shù)據(jù)集大小卻很有限。

數(shù)據(jù)分析是對(duì)數(shù)據(jù)中的某些特征進(jìn)行分析和挖掘,找出數(shù)據(jù)間的規(guī)律和特征,從而為數(shù)據(jù)的顯示做準(zhǔn)備。數(shù)據(jù)分析方法包括基于降維的數(shù)據(jù)分析和基于非降維的數(shù)據(jù)分析。其中,基于降維的數(shù)據(jù)分析方法通過(guò)分析數(shù)據(jù)之間的特征,將數(shù)據(jù)從高維降低或者映射到低維,這樣既保留數(shù)據(jù)的主要特征,又能為分析數(shù)據(jù)和顯示數(shù)據(jù)帶來(lái)方便。目前基于降維的數(shù)據(jù)分析方法包括主成分分析(Principal Component Analysis,PCA)、投影尋蹤(Project Pursuit,PP)、多維尺度[8](Multi-Dimensional Scaling,MDS)、自組織映射SOM[9](Self-organizing Mapping,SOM)、局部線性嵌入(LLE)以及基于神經(jīng)網(wǎng)絡(luò)和基于分形的降維方法等。文獻(xiàn)[10]提出一種結(jié)合PCA和平行坐標(biāo)的數(shù)據(jù)可視化方法,先利用PCA方法對(duì)高維數(shù)據(jù)進(jìn)行有效的降維處理,將降維后的數(shù)據(jù)進(jìn)行平行坐標(biāo)可視化展示。該方法能有效地揭示高維數(shù)據(jù)之間的關(guān)系。而文獻(xiàn)[11]結(jié)合SOM的降維映射技術(shù)對(duì)大數(shù)據(jù)進(jìn)行分類,然后利用平行坐標(biāo)系進(jìn)行顯示,取得了很好的效果?；诮稻S的數(shù)據(jù)分析技術(shù),雖然可以保留高維數(shù)據(jù)的主要特征,降低維度,為數(shù)據(jù)的顯示帶來(lái)方便,但是會(huì)損失部分原有數(shù)據(jù)所攜帶的信息,最終的數(shù)據(jù)準(zhǔn)確與否及顯示的效果的好壞,與原數(shù)據(jù)的特點(diǎn)以及選取的降維方法有直接的關(guān)系,并且最終會(huì)影響決策者的決策。

而基于非降維的數(shù)據(jù)分析方法則通過(guò)分析高維數(shù)據(jù)的特征如維與維之間的相關(guān)度和距離等,并利用這些特征,指導(dǎo)數(shù)據(jù)的重新組織排列。與基于降維的數(shù)據(jù)分析方法相比,其最大的區(qū)別是基于非降維的數(shù)據(jù)分析方法只會(huì)根據(jù)數(shù)據(jù)本身分析出來(lái)的特征,對(duì)數(shù)據(jù)進(jìn)行重新調(diào)整與組織,而不用減少數(shù)據(jù)的維度,保持原有數(shù)據(jù)所攜帶的信息的完整性。文獻(xiàn)[12]針對(duì)高維多目標(biāo)優(yōu)化結(jié)果的顯示問(wèn)題,首先將數(shù)據(jù)序列化,然后采用非降維的數(shù)據(jù)分析技術(shù),引導(dǎo)數(shù)據(jù)集的行和列的重新排列組合,將相關(guān)度高的行和列放在一起,最后采用熱圖將最終結(jié)果進(jìn)行顯示,取得了很好的顯示效果。盡管非降維的數(shù)據(jù)分析方法有種種優(yōu)點(diǎn),但其缺點(diǎn)也是明顯的。首先其對(duì)于數(shù)據(jù)的分析不夠深入,不能有效挖掘出數(shù)據(jù)的內(nèi)在特征。另外,若高維數(shù)據(jù)中存在冗余數(shù)據(jù),其可能會(huì)干擾數(shù)據(jù)的分析,影響數(shù)據(jù)維之間的相關(guān)度和距離等特征。

本文針對(duì)數(shù)據(jù)分析方法的優(yōu)缺點(diǎn),提出一種新的結(jié)合降維和非降維的可視化方法,即采用基于降維的數(shù)據(jù)分析方法,獲取數(shù)據(jù)的特征,并以此來(lái)引導(dǎo)數(shù)據(jù)的重新排列和組織,而無(wú)需減少數(shù)據(jù)的維度,損失信息。

2 相關(guān)理論

2.1 多目標(biāo)優(yōu)化問(wèn)題

對(duì)于一個(gè)具有M維目標(biāo)的最小化函數(shù),可以記為:

其中,F(x)(x)為M維的目標(biāo)函數(shù)向量;fi(x)為第i維的目標(biāo)函數(shù);x為n維決策向量;Xn為決策空間,當(dāng)函數(shù)的目標(biāo)個(gè)數(shù)M≥4時(shí),稱其為高維多目標(biāo)優(yōu)化問(wèn)題。

2.2 主成分分析

主成分分析(PCA)是采取一種數(shù)學(xué)降維的方法,找出幾個(gè)綜合變量來(lái)代替原來(lái)眾多的變量,使這些綜合變量盡可能多地反映原來(lái)變量的信息量,而且彼此之間相互獨(dú)立。通常數(shù)學(xué)上的處理方法就是將原來(lái)的變量做線性組合,適當(dāng)調(diào)整組合系數(shù),使新的變量指標(biāo)之間相互獨(dú)立且代表性最好。

對(duì)于一組數(shù)據(jù)矩陣X由M個(gè)變量X1,X2,…, XM,Xi=(x1i,x2i,…,xni)T和n個(gè)樣本組成,其中:

新的綜合變量為F,F用以下矩陣表示:

主成分分析就是要找出一個(gè)系數(shù)矩陣A,A用以下矩陣表示:

使得F為X中所有列的線性組合:

簡(jiǎn)寫(xiě)為:

其中,j=1,2,…,M。

系數(shù)矩陣由以下原則決定:

(1)Fi,Fj互不相關(guān)(i≠j,i,j=1,2,…,M)。

(2)F1,F2,…,FM的方差滿足。Var(F1)≥Var(F2)≥…≥Var(FM)。

由以上分析可看出F1,F2,…,FM互不相關(guān),F1的方差Var(F1)最大,則F1包含的信息越多,故稱F1為第一主成分,F2為第二主成分,依此類推?？筛鶕?jù)實(shí)際情況選取F中前幾個(gè)變量,代替原來(lái)所有的變量。

2.3 熱圖

熱圖是一種常見(jiàn)的可視化方法,其可以將多維的數(shù)據(jù)以二維的方式完全直觀地呈現(xiàn)出來(lái),并用顏色深淺表示數(shù)值的大小。對(duì)于數(shù)據(jù)(200行9列),其熱圖可視化如圖1所示,圖中行列分別代表數(shù)據(jù)的行列,每個(gè)數(shù)據(jù)的大小用顏色的深淺表示。與一些降維可視化方法相比,熱圖可以同時(shí)表示大量的數(shù)據(jù),而不損失信息。

圖1 熱圖模型

3 基于PCA的熱圖可視化方法

3.1 基于PCA的熱圖可視化方法具體步驟

對(duì)于高維多目標(biāo)算法求得的前沿?cái)?shù)據(jù)集F,表示為如下:

其中,n＞M,n為解的個(gè)數(shù),M為目標(biāo)個(gè)數(shù)。

本文可視化方法有5個(gè)步驟構(gòu)成:數(shù)據(jù)預(yù)處理→PCA處理→排序→分級(jí)聚類→熱圖顯示。

(1)數(shù)據(jù)預(yù)處理

數(shù)據(jù)標(biāo)準(zhǔn)化預(yù)處理。將原數(shù)據(jù)集F標(biāo)準(zhǔn)化處理,使其變?yōu)榉讲顬?,標(biāo)準(zhǔn)差為1的矩陣Z,其計(jì)算公式如下:

其中,1≤i≤n;1≤j≤M;fij為原數(shù)據(jù)F中第i行第j列數(shù)據(jù);Ti為F中第i行的均值;σi為第i行的標(biāo)準(zhǔn)差。

(2)PCA處理

對(duì)于上一步求得矩陣Z,計(jì)算相關(guān)的協(xié)方差矩陣B后,求出協(xié)方差矩陣的所有特征值組成的向量A,及其對(duì)應(yīng)的特征向量組成的矩陣C(M行M列),公式如下:

其中,a1,a2,…,aM為協(xié)方差的特征值;C1,C2,…,CM為特征值對(duì)應(yīng)的特征向量。

根據(jù)特征值,計(jì)算轉(zhuǎn)換后的數(shù)據(jù)矩陣Y,計(jì)算方法如下:

根據(jù)式(13)計(jì)算出Y中每一列對(duì)應(yīng)的貢獻(xiàn)率組成矩陣λ,λ=(λ1,λ2,…,λi,…,λM),其中,1≤i≤M。

(3)排序

對(duì)貢獻(xiàn)率λi按照從大到小的順序排列,并相應(yīng)的調(diào)整其對(duì)應(yīng)在Y中列的順序,假設(shè)調(diào)整順序后的矩陣為Y′,其中:

貢獻(xiàn)率越大,Y中數(shù)據(jù)列在Y′中對(duì)應(yīng)的數(shù)據(jù)列排序越靠前,即此列主成分所占比重越大,在熱圖中顯示順序越靠前。

(4)分級(jí)聚類

為達(dá)到滿意的可視化效果,還需要對(duì)Y′繼續(xù)處理,即按行間的相似度,進(jìn)行重新移動(dòng)排序,重新組織行的順序,將相關(guān)度大的行盡量挪到一起,方便決策者的同時(shí),達(dá)到最好的顯示效果。

在本文中,將采用分級(jí)聚類算法[13],對(duì)Y′進(jìn)行處理。由于此時(shí)采用的分級(jí)聚類算法是根據(jù)距離來(lái)判斷數(shù)據(jù)之間的相近度,因此對(duì)距離計(jì)算方法加以改進(jìn),在計(jì)算距離時(shí)加入了主成分貢獻(xiàn)率因素,具體如下:

對(duì)于由式(17)得到的數(shù)據(jù)矩陣Y′,由式(16)可知,Y′每一列的權(quán)重大小也就是其貢獻(xiàn)率,為λ= (λ1,λ2,…,λM),首先Y′每一列與對(duì)應(yīng)的貢獻(xiàn)率相乘,得:

利用以下公式計(jì)算λnew中任意兩行i,j之間的距離:

最后分級(jí)聚類算法以公式計(jì)算行之間的距離,來(lái)判斷數(shù)據(jù)間的相似度,設(shè)經(jīng)過(guò)處理后得到的數(shù)據(jù)為Y",Y"也是n行M列的矩陣。

(5)熱圖顯示

經(jīng)過(guò)以上處理后,利用熱圖對(duì)最終得到的結(jié)果Y"進(jìn)行顯示。

3.2 方法證明

由以上步驟可知,熱圖最終顯示的是經(jīng)過(guò)處理后的數(shù)據(jù),而不是原始數(shù)據(jù)。原數(shù)據(jù)經(jīng)過(guò)PCA處理后得到轉(zhuǎn)換后的數(shù)據(jù),利用分級(jí)聚類算法對(duì)轉(zhuǎn)換后數(shù)據(jù)的所有行進(jìn)行計(jì)算時(shí),采用了基于貢獻(xiàn)率的距離計(jì)算方法。那么加入了貢獻(xiàn)率因素相比于沒(méi)有加入貢獻(xiàn)率因素的距離計(jì)算方法,分級(jí)聚類結(jié)果是否受到影響,從而影響最終的顯示效果。

以上過(guò)程相當(dāng)于已知原數(shù)據(jù)F,經(jīng)PCA處理轉(zhuǎn)換后的數(shù)據(jù)為Y,轉(zhuǎn)換矩陣為C,Y中每一列對(duì)應(yīng)的貢獻(xiàn)率組成向量λ,λ=(λ1,λ2,…,λi,…,λM),證明加入貢獻(xiàn)率因素,即λ中每一個(gè)值作為對(duì)應(yīng)Y中每一列的權(quán)重,然后計(jì)算每列之間的距離,此距離與不加貢獻(xiàn)率因素相比,對(duì)分級(jí)聚類算法處理沒(méi)有影響,對(duì)最終熱圖顯示結(jié)果沒(méi)有影響。

證明如下:

根據(jù)式(15)可知,PCA處理轉(zhuǎn)換后的數(shù)據(jù)為Y,計(jì)算公式如下:

由式(13)可求出C-1=(C1,C2,…,CM),則原數(shù)據(jù)F滿足:

加入貢獻(xiàn)率因素λ=(λ1,λ2,…,λM),F中每一列與相應(yīng)的貢獻(xiàn)率相乘,得到新的數(shù)據(jù)Fnew。

任意兩行i與j的距離Distance(i,j)為:

設(shè)變量H,則:

未加入貢獻(xiàn)率因素是任意兩行i與j的距離為D(i,j):

則最終加入貢獻(xiàn)率因素的距離公式可寫(xiě)為:

由式(24)和式(25)可知,加入貢獻(xiàn)率因素轉(zhuǎn)換后數(shù)據(jù)行之間的距離相比于不加貢獻(xiàn)率因素?cái)?shù)據(jù)行之間的距離,其只跟常數(shù)因素H有關(guān)。它們之間的距離會(huì)按照相同的比例H增大或縮小,并不會(huì)對(duì)分級(jí)聚類算法判斷距離產(chǎn)生影響,對(duì)最終的熱圖顯示效果沒(méi)有影響,原命題得到證明。

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

分別利用6目標(biāo)和8目標(biāo)的DTLZ2問(wèn)題,得到2組高維解集,其中,DTLZ2_6D數(shù)據(jù)由254個(gè)解、6個(gè)目標(biāo)組成,DTLZ2_8D數(shù)據(jù)由380樣本、8個(gè)目標(biāo)組成。

對(duì)于原始數(shù)據(jù)DTLZ2_6D,由圖2處理過(guò)程中得到的3張熱圖的變化(圖2(a)→圖2(b)→圖2(c))可知:(1)原始數(shù)據(jù)在未經(jīng)處理,在熱圖中顯示效果不理想如圖2(a),只能知道數(shù)值大小,不能有效獲知數(shù)據(jù)之間的關(guān)系;(2)經(jīng)PCA處理后,能得到轉(zhuǎn)換后的數(shù)據(jù),和對(duì)應(yīng)的貢獻(xiàn)率表,如表1所示。此時(shí)得到的熱圖圖2(b)相比于熱圖圖2(a),在整體顯示效果上相當(dāng),但通過(guò)圖2(b)能直接獲知轉(zhuǎn)換后每個(gè)目標(biāo)的貢獻(xiàn)率;(3)數(shù)據(jù)在經(jīng)過(guò)改進(jìn)的分級(jí)聚類算法處理后,得到最終顯示圖2(c)。圖2(c)相比圖2(b),改變了數(shù)據(jù)行之間的順序,其顯示效果得到極大的提高,在列的維度上,知道每個(gè)目標(biāo)的的主成分的貢獻(xiàn)程度,在行的維度上,知道解的相近程度,彼此越靠近,反映在如圖上就是一大片色塊顏色越相近;(4)用戶在最終的圖上能方便地挑選需要的解,作出最終決策。如果要求第3目標(biāo)數(shù)值較大,而其他盡量小,則可以在圖2(c)中選擇第2列最靠下位置的幾組解。

圖2 熱圖變化1

表1 DTLZ2_6D 6個(gè)目標(biāo)對(duì)應(yīng)的貢獻(xiàn)率

而對(duì)于原始DTLZ2_8D,經(jīng)過(guò)與DTLZ2_6D相同的處理,也得到3張熱圖和一個(gè)貢獻(xiàn)率表。從圖3的變化過(guò)程圖3(a)→圖3(b)→圖3(c),也可與DTLZ2_6D得到類似的結(jié)論,顯示效果逐漸提高,熱圖提供的信息遞增。從最終結(jié)果能夠直觀地獲取目標(biāo)的貢獻(xiàn)率,解之間的相關(guān)度,方便用戶挑選滿意的解。DTLZ2_8D 8個(gè)目標(biāo)對(duì)應(yīng)的貢獻(xiàn)率如表2所示。

圖3 熱圖變化2

表2 DTLZ2_8D 8個(gè)目標(biāo)對(duì)應(yīng)的貢獻(xiàn)率

從以上2組實(shí)驗(yàn)可以看出,本文提出的可視化方法既能使用戶知道轉(zhuǎn)換后每個(gè)目標(biāo)所占的貢獻(xiàn)率,又能取得較滿意的視覺(jué)效果,方便用戶理解數(shù)據(jù)的整體分布并作出決策。

5 結(jié)束語(yǔ)

本文結(jié)合基于降維和非降維的數(shù)據(jù)分析技術(shù),提出一種新的高維多目標(biāo)優(yōu)化的可視化方法。該方法能夠有效地揭示數(shù)據(jù)特征,且獲得較好的顯示效果,最終能夠快速地幫助決策者進(jìn)行決策。然而當(dāng)高維多目標(biāo)優(yōu)化解集中目標(biāo)之間相關(guān)性較差或彼此獨(dú)立時(shí),該方法不能取得較滿意效果。今后的研究將繼續(xù)完善該方法,針對(duì)擁有獨(dú)特特征的高維多目標(biāo)優(yōu)化解集采用不同的數(shù)據(jù)分析方法和顯示工具,并且改進(jìn)分級(jí)聚類算法,優(yōu)化顯示效果,從而更加方便有效地幫助決策者分析和理解數(shù)據(jù)并進(jìn)行最終的決策。

[1] 蘇勇彥.單目標(biāo)、多目標(biāo)優(yōu)化進(jìn)化算法及其應(yīng)用[D].武漢:武漢理工大學(xué),2007.

[2] 孔維健,丁進(jìn)良,柴天佑.高維多目標(biāo)優(yōu)化問(wèn)題的研究概述[J].控制與決策,2010,25(3):321-326.

[3] Pryke A,Mostaghim S,Nazemi A.Heatmap Visualization of Population Based Multi Objective Algorithms[C]// Proc.of EMO’06.Matsushima,Japan:[s.n.],2006: 361-375.

[4] Xu Yonghong,Hong Wenxue,Chen Na,et al.Parallel Filter:A Visual Classifier Based on Parallel Coordinates and Multivariate Data Analysis[C]//Proc.of International Conferenceon IntelligentComputing.Qingdao,China: [s.n.]:2007:1172-1183.

[5] 洪文學(xué).基于多元統(tǒng)計(jì)圖表示原理的信息融合和模式識(shí)別技術(shù)[M].北京:國(guó)防工業(yè)出版社,2008.

[6] Inselberg A,Dimsdale B.Parallel Coordinates:A Tool for Visualizing Multi-dimensionalGeometry[C]// Proc.of the 1st IEEE Conference on Visualization.San Francisco,USA:[s.n.],1990:361-371.

[7] Johansson J, Treloar R, Jern M.Integration of Unsupervised Clustering, Interaction and Parallel Coordinates for the Exploration of Large Multivariate Data[C]//Proc.of IEEE Symposium on Information Visualization.[S.1.]:IEEE Press,2004:215-222.

[8] Gabriel T R.Rule Visualization Based on Multidimensional Scaling[C]//Proc.of IEEE International Conferenceon Fuzzy Systems.Vancouver,Canada: IEEE Press,2006:333-345.

[9] Kohonen T.Self-organising Maps[M].Berlin,Germany: Springer,1995.

[10] 雷君虎,楊家紅,鐘堅(jiān)成,等.基于PCA和平行坐標(biāo)的高維數(shù)據(jù)可視化[J].計(jì)算機(jī)工程,2011,37(1): 48-50.

[11] Fonseca C M,Fleming P J.Genetic Algorithmsfor Multiobjective Optimization:Formulation,Discussion and Generalization[C]//Proc.of the 5th International Conference on Genetic Algorithms.[S.1.]:Morgan Kauffman Press,1993:416-423.

[12] Walker D J,VersonR M,JonathanE.Visualizing Mutually Nondominating Solution Sets in Manyobjective Optimization[J].IEEE Transactionson Evolutionary Computation,2013,17(2):165-184.

[13] 段明秀.層次聚類算法的研究及應(yīng)用[D].長(zhǎng)沙:中南大學(xué),2009.

編輯 索書(shū)志

Visualization Method of High Dimensional Multi-objective Optimization Based on Principal Component Analysis

LIU Guang,CHEN Zi-yu
(College of Computer Science,Chongqing University,Chongqing 400044,China)

It is very difficult to visualize the high dimensional solution set of the multi-objective optimization problem for its large number of objective and solution.To solve the above problems,this paper proposes a new method to visualize the high dimensional solution sets with dimensionality reduction and non-dimensionality reduction techniques of data analysis.This method pretreats the solution set of the multi-objective optimization algorithm,uses Principal Component Analysis(PCA)to analyze the characteristics of the data and get the converted data and its corresponding contribution rate.According to the contribution rate order,it adjusts the the order of columns of the converted data,and calculates the distance between the rows of the converted data with the contribution rate use and runs the hierarchical clustering algorithms based on the row distance to reorder the rows and reorganize the data.It displays the result on heat map.Experimental results show that the method can let the user know the contribution rate of the each converted target, offer satisfactory visual effects,facilitate the understanding of the distribution of the data and make decisions.

Principal Component Analysis(PCA);heat map;high dimensional multi-objective optimization; visualization;hierarchical clustering;dimension reduction

1000-3428(2014)10-0192-06

A

TP18

10.3969/j.issn.1000-3428.2014.10.036

劉 廣(1987-),男,碩士研究生,主研方向:多目標(biāo)優(yōu)化;陳自郁,講師、博士。

2013-10-14

2013-12-10E-mail:guangliu.123@163.com

中文引用格式:劉 廣,陳自郁.基于PCA的高維多目標(biāo)優(yōu)化可視化方法[J].計(jì)算機(jī)工程,2014,40(10):192-197.

英文引用格式:Liu Guang,Chen Ziyu.Visualization Method of High Dimensional Multi-objective Optimization Based on Principal Component Analysis[J].Computer Engineering,2014,40(10):192-197.