李輝輝,劉延龍

(東北林業(yè)大學(xué))

?

三維可視化在經(jīng)典優(yōu)化算法中的應(yīng)用

李輝輝*,劉延龍

(東北林業(yè)大學(xué))

三維可視化(科學(xué)可視化)已經(jīng)成為現(xiàn)代科學(xué)研究的重要課題之一，多維函數(shù)問題在現(xiàn)實(shí)生活中層出不窮，將多維函數(shù)問題進(jìn)行降維從而應(yīng)用在三維可視化中就成為解決多維問題重要的一步.這個(gè)過程最主要的就是要求通過適當(dāng)?shù)慕稻S方法將大量的多維數(shù)據(jù)降到人們能夠利用或者方便處理的程度.根據(jù)規(guī)劃中目標(biāo)函數(shù)的線性性，線性降維算法和非線性降維算法已經(jīng)成為解決多維函數(shù)問題的主要方法，將通過經(jīng)典優(yōu)化算法將非線性無約束規(guī)劃問題進(jìn)行降維，從而使該類多維問題在三維圖像中實(shí)現(xiàn)可視化.

三維可視化;降維;非線性無約束規(guī)劃

0 引言

計(jì)算科學(xué)與信息技術(shù)[1]已經(jīng)歷經(jīng)了幾十年的發(fā)展，給人類社會(huì)的發(fā)展帶來了極大的影響.隨著現(xiàn)代的數(shù)據(jù)采集、數(shù)據(jù)儲(chǔ)存以及數(shù)據(jù)管理等技術(shù)的日趨成熟，人們獲取和收集數(shù)據(jù)的能力得到了巨大的提升，獲取的數(shù)據(jù)數(shù)量正以指數(shù)級(jí)的形式增加.無論是科學(xué)研究領(lǐng)域還是社會(huì)生活等方面都積累了大量復(fù)雜的數(shù)據(jù).在科學(xué)研究和實(shí)際工程中，很多數(shù)據(jù)集具有多維的特點(diǎn).如：圖像分析、計(jì)算機(jī)視覺、地震屬性、三維模型的分類與檢索.這些多維特征能夠提供更為豐富和詳細(xì)的信息，理論上會(huì)給提高算法的準(zhǔn)確性帶來很大幫助.這些豐富的數(shù)據(jù)資料給人們帶來便利但同時(shí)也帶來了一大堆的難題，比如信息過量、數(shù)據(jù)難以處理、有價(jià)值的信息淹沒在海量的數(shù)據(jù)中、數(shù)據(jù)難以取舍等.面對(duì)“過多”的數(shù)據(jù)信息，如果缺乏合理的分析和處理手段，就無法發(fā)掘出數(shù)據(jù)中隱含的潛在系和規(guī)則，也無法據(jù)此對(duì)未來的發(fā)展趨勢做出預(yù)測.這就直接導(dǎo)致所謂的“數(shù)據(jù)富但知識(shí)匱乏”的現(xiàn)象.因此，如何對(duì)這些豐富的數(shù)據(jù)資源進(jìn)行合理的分析，挖掘出數(shù)據(jù)中蘊(yùn)含的有效信息已經(jīng)成為研究者和技術(shù)專家所面臨的挑戰(zhàn).為了解決這一問題，可以首先將數(shù)據(jù)降到低維空間，然后得到低維特征進(jìn)行既定的學(xué)習(xí)或者挖掘任務(wù).有效的數(shù)據(jù)降維技術(shù)能夠探索出原始數(shù)據(jù)的內(nèi)在結(jié)構(gòu)和聯(lián)系，不僅可以消除數(shù)據(jù)間的冗余，以簡化數(shù)據(jù)，提高計(jì)算效率，還能夠大大改善數(shù)據(jù)的可理解性，提高學(xué)習(xí)算法的精度.

降維算法間接地將多維問題進(jìn)行了轉(zhuǎn)化，使得多維問題更加容易被研究，而將多維問題進(jìn)行降維在三維圖形中可視化[2]使得研究結(jié)果更加清晰，從而讓人們更直接的解決多維問題.根據(jù)多維問題的線性性，將降維算法分為線性降維算法和非線性算法.線性降維算法包括：PCA主成分分析[3]和LDA線性判別分析[4]等，非線性降維算法包括：SOFM自組織特征映射、主曲線以及LLE局部線性嵌入ISOMAP等距映射和LE拉普拉斯特征值映射等.該文將從非線性無約束問題規(guī)劃入手，研究降維算法，改進(jìn)并進(jìn)行應(yīng)用.

1 降維算法

1.1 n維歐氏空間定義

設(shè)V是實(shí)數(shù)域R上的線性空間(或稱為向量空間)，如果對(duì)V中的任意兩個(gè)元素α,β確定的實(shí)數(shù)(α,β)與它們對(duì)應(yīng)，且滿足如下關(guān)系：

(1)(α,β)=(β,α);

(2)(kα,β)=k(α,β),k∈R;

(3)(α+β,τ)=(α,τ)+(β,τ),τ∈V.

(4)(α,α)≥0,當(dāng)且僅當(dāng)α=0時(shí),(α,α)=0.

則稱(α,β)為α與β的內(nèi)積，定義了內(nèi)積的線性空間V稱為歐幾里得空間，簡稱為歐氏空間.所以說空間可以被擴(kuò)展來應(yīng)用于任何有限維度，而這種空間就叫做n維歐幾里得空間(簡稱n維空間)或有限維實(shí)內(nèi)積空間.

1.2 超平面[5]的定義

超平面是指n維歐氏空間中余維度等于1的線性子空間，它是由平面中的直線、空間中的平面在n維歐氏空間中的推廣得來的，在形如{x/aTx=b}的一個(gè)集合中，其中a是歐氏空間Rn中的一個(gè)非零向量，b是一個(gè)標(biāo)量，這個(gè)集合就叫作n維歐氏空間中的超平面.超平面是從n維空間到n-1維空間的一個(gè)映射子空間，它有一個(gè)n維向量和一個(gè)實(shí)數(shù)定義.

1.3 n維歐氏空間向量的二范數(shù)

范數(shù)是表示具有“長度”概念的函數(shù).在泛函分析、線性代數(shù)及相關(guān)的數(shù)學(xué)領(lǐng)域中它指的是一個(gè)函數(shù)，它表示為矢量空間內(nèi)的所有矢量賦予非零的正長度或大小.

若X是數(shù)域K上的線性空間，泛函‖·‖： X→R滿足：

(2)正齊次性：‖cx‖=|c|·‖x‖,c∈R.

(3)次可加性(三角不等式)：‖x+y‖≤‖x‖+‖y‖.

那么‖·‖稱為X上的一個(gè)范數(shù).范數(shù)與內(nèi)積、度量、拓?fù)涫窍嗷ヂ?lián)系的.

n維歐氏空間向量的2-范數(shù)：

設(shè)x=(x1,x2,…,xn)， ‖x‖2=(|x1|^2+

|x2|^2+…+|xn|^2)^1/2

1.4 克萊姆法則

1.5 基本思路

已知X(0)和L，其中 X(0)是歐式空間中超平面上的一點(diǎn)，L是這個(gè)超平面的一個(gè)法線方向，求過X(0)點(diǎn)的某單位向量 α和β，使得α⊥L、 和β⊥L.由此可知，超平面上的任意一點(diǎn)都可由α和β這兩個(gè)向量和定點(diǎn)X(0)來確定，利用α和β則可構(gòu)建三維圖像，從而使多維函數(shù)實(shí)現(xiàn)可視化.

具體策略如下[6]：

由超平面定義 ，有

(X-X(0))TL=0

(1)

由于L≠0∈Rn,設(shè)lj=max(|l1|,|l2|,|l3|，…,|ln|),必有l(wèi)j>0,

又令

(2)

將(2)式帶入(1)式有

(3)

(4)

設(shè)lk=max(|l1|,…,|lj-1|,|lj+1|,…|ln|)

(5)

將(5)式代入(1)式可得

(6)

由α⊥β以及(2)式和(5)式，可得

(X(1)-X(0))T(X(2)-X(0))=0

(2-n)·lj

(7)

根據(jù)克萊姆法則：

(10)

此時(shí)，n維函數(shù)F(X)的自變量取值范圍：

X=Cα·α+Cβ·β+X(0)

(11)

式中Cα、Cβ均為某一取值范圍，例如：(-0.5,0.5)等.

綜上可知：根據(jù)1可以計(jì)算出α、β兩個(gè)向量，以Cα、Cβ兩個(gè)變量得出X，從而知道f (X)，運(yùn)用matlab程序[7]繪制以Cα、Cβ和f(X)為坐標(biāo)的三維圖形，從而使非線性無約束規(guī)劃在三維空間實(shí)現(xiàn)可視化.

2 算法仿真實(shí)驗(yàn)

式中X(0)=[1.0,1.0,1.0,1.0]T

L(1)=[0.5,0.8,0.1,0.3]T

L(2)=[0.5,-0.8,0.1,-0.3]T

Cα和Cβ均屬于(-0.7，0.7).

當(dāng)L(1)=[0.5,0.8,0.1,0.3]T時(shí)， 得圖1所示圖像.

圖1 垂直于L(1)方向的f1(X)的三維圖像

當(dāng)L(2)=[0.5,-0.8,0.1,-0.3]T時(shí)，得圖2所示圖像

圖2 垂直于L(2)方向的f1(X)的三維圖像

式中X(0)=[1.2,1.2,1.2,1.2]T,

L(1)=[0.9,0.2,0.5,0.7]T,

L(2)=[-0.9,0.2,-0.5,0.7]T.

Cα和Cβ均屬于(-0.9,0.9).

當(dāng)L(1)=[0.9,0.2,0.5,0.7]T時(shí)， 得圖3所示圖像.

圖3 垂直于L(1)方向的f 2(X)的三維圖像

當(dāng)L(2)=[-0.9,0.2,-0.5,0.7]T時(shí)， 得圖4所示圖像.

圖4 垂直于L(2)方向的f 2(X)的三維圖像

式中X(0)=[0.8,0.8,0.8,0.8,0.8,0.8,0.8]T;

L(1)=[0.1,0.3,0.5,0.7,0.9,0.6,0.4]T;

L(2)=[-0.1,0.3,-0.5,0.7,-0.9,0.6,-0.4]T,

Cα和Cβ均屬于(-0.6，0.6).

當(dāng)L(1)=[0.1,0.3,0.5,0.7,0.9,0.6,

0.4]T時(shí)，得圖5所示圖像.

圖5 垂直于L(1)方向的f 3(x)的三維圖像

當(dāng)L(2)=[-0.1,0.3,-0.5,0.7,-0.9,0.6,-0.4]T時(shí)， 得圖6所示圖像.

圖6 垂直于L(2)方向的f3(X)的三維圖像

3 降維算法的改進(jìn)

從而可知在上述算法中α、β是由L確定的，如果將(2)和(5)式中的1變?yōu)閷儆?0，1)的任意數(shù)r，則對(duì)該種降維算法進(jìn)行了改進(jìn).具體策略如下：

設(shè)r∈(0,1)，有

就例1L(1)=[0.5,0.8,0.1,0.3]T方向來研究：

當(dāng)r不同時(shí)的四種三維圖形(如圖7-10所示)的比較：

圖7 當(dāng)r=1時(shí)f 1(X)的三維圖像

圖8 當(dāng)r=0.1時(shí)f1(X)的三維圖像

圖9 當(dāng)r=0.5時(shí)f1(X)的三維圖像

圖10 當(dāng)r=0.9時(shí)f1(x)的三維圖像

由此可知，r的取值直接影響到了繪制出的圖形.隨著r的變化，按照matlab程序所繪制出來的圖形是不一樣的，從而也說明了該非線性無約束規(guī)劃的解也受到了影響.從圖形的比較中可以看出在解的影響上該文所描述的降維算法中設(shè)定條件占了很大一部分原因.

4 結(jié)束語

隨著計(jì)算機(jī)技術(shù)的發(fā)展，多維數(shù)據(jù)問題在現(xiàn)實(shí)應(yīng)用中層出不窮，三維數(shù)據(jù)可以在人腦中產(chǎn)生圖像便于分析，而多維的數(shù)據(jù)很難讓人們直接理解，所以在醫(yī)學(xué)、科學(xué)研究、建筑學(xué)、氣象學(xué)、生物學(xué)等方面的各種應(yīng)用中出現(xiàn)的多維數(shù)據(jù)能夠通過降維算法進(jìn)行降維，用三維圖像的形式展示出來則可以給實(shí)驗(yàn)研究帶來很大的方便[8].該文在基于使多維函數(shù)實(shí)現(xiàn)三維可視化的基礎(chǔ)上，分析了一種降維算法的具體方案.論文的研究方法通用性極高，但根據(jù)論文中降維算法的研究也發(fā)現(xiàn)此降維算法對(duì)規(guī)劃問題中解的可行性對(duì)已知條件有很強(qiáng)的依賴性.

[1] 喬立山. 基于圖的降維技術(shù)研究及應(yīng)用[D]. 南京：南京航空航天大學(xué), 2009.

[2] 石教英. 科學(xué)計(jì)算可視化算法與系統(tǒng)[M].北京：科學(xué)出版社, 1996.

[3] Timmerman M E. Bookreview. Principal Component Analysis (2nd ed.). I.T. Jolliffe. New York: Springer-Verlag, 2002. ISBN 0-387-95442-2. XXIX + 486 pp.[J]. Journal of the American Statistical Association, 2003, 464,vol.98.

[4] Belhumeur P N, Hespanha J P, Kriegman D J. Eigenfaces vs. Fisherfaces: Recognition using class specific linear projection[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1997, 19(7):711-720.

[5] 余建明, 姜廣峰. 超平面構(gòu)形的可約性[J]. 中國科學(xué),2006(12):1422-1430.

[6] 鄧揚(yáng)晨, 張衛(wèi)紅, 錢衛(wèi),等. 多維函數(shù)圖形的一種三維可視化方法[J]. 西北工業(yè)大學(xué)學(xué)報(bào), 2003, 21(3):368-371.

[7] 趙海濱. MATLAB應(yīng)用大全[M]. 北京：清華大學(xué)出版社, 2012.

[8] 宋靚. 降維方法及非線性降維方法舉例[J].中國高新技術(shù)企業(yè), 2011(10):46-47.

(責(zé)任編輯：于達(dá))

The Application of 3D Visualization in Classical Optimization Algorithm

Li Huihui， Liu Yanlong

(Northeast Forestry University)

Three-dimensional visualization has become one of the important subjects of modern scientific research. Multidimensional function has become an endless problem in real life. It is an important step for the dimensionality reduction of the multi-dimensional function applying into the 3D visualization, and the main requirement of this process is through the proper method of dimensionality reduction to make a lot of multidimensional data more convenient for people to use or much easy to deal with. According to the linear programming in objective function, linear dimensional reduction algorithm and nonlinear dimensional reduction algorithm have become the main method to solve the problem of multi-dimensional function. In this article, dimensionality reduction of unconstrained nonlinear programming through classical optimization algorithm is realized, which makes this kind of multidimensional problems visualized in the 3D image.

Three-dimensional visualization; Dimensionality reduction; Nonlinear unconstrained programming

2016-01-09

*通訊作者：1163727319@qq.com

O18

A

1000-5617(2016)02-0023-06