李輝輝,劉延龍

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

?

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

李輝輝*,劉延龍

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

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

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

0 引言

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

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

1 降維算法

1.1 n維歐氏空間定義

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

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

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

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

(4)(α,α)≥0,當且僅當α=0時,(α,α)=0.

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

1.2 超平面[5]的定義

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

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

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

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

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

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

那么‖·‖稱為X上的一個范數(shù).范數(shù)與內(nèi)積、度量、拓撲是相互聯(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)是歐式空間中超平面上的一點，L是這個超平面的一個法線方向，求過X(0)點的某單位向量 α和β，使得α⊥L、 和β⊥L.由此可知，超平面上的任意一點都可由α和β這兩個向量和定點X(0)來確定，利用α和β則可構(gòu)建三維圖像，從而使多維函數(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)

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

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

(11)

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

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

2 算法仿真實驗

式中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).

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

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

當L(2)=[0.5,-0.8,0.1,-0.3]T時，得圖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).

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

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

當L(2)=[-0.9,0.2,-0.5,0.7]T時， 得圖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).

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

0.4]T時，得圖5所示圖像.

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

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

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

3 降維算法的改進

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

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

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

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

圖7 當r=1時f 1(X)的三維圖像

圖8 當r=0.1時f1(X)的三維圖像

圖9 當r=0.5時f1(X)的三維圖像

圖10 當r=0.9時f1(x)的三維圖像

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

4 結(jié)束語

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

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

[2] 石教英. 科學(xué)計算可視化算法與系統(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] 鄧揚晨, 張衛(wèi)紅, 錢衛(wèi),等. 多維函數(shù)圖形的一種三維可視化方法[J]. 西北工業(yè)大學(xué)學(xué)報, 2003, 21(3):368-371.

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

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

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

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